백준 8112 : 0과 1 - 2

https://www.acmicpc.net/problem/8112

8112번: 0과 1 - 2

 

풀이는 이전 포스트와 동일합니다.

https://kukekyakya.tistory.com/entry/%EB%B0%B1%EC%A4%80-8111-0%EA%B3%BC-1

 

범위만 수정해주면 통과할 수 있었습니다.

#include <iostream>
#include <queue>
#include <cstring>
bool visit[1000000];
int t, n, p[1000000] = { 0,-1 }, num[1000000] = { 0,1 };
void print(int val) {
	if (val == -1) return;
	print(p[val]);
	printf("%d", num[val]);
}
bool bfs() {
	if (n == 1) { p[0] = -1, num[0] = 1; return true; }
	memset(visit, false, sizeof(visit));
	visit[1] = true;
	std::queue<int> q;
	q.push(1);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (!x) return true;
		for (int i = 0; i < 2; i++) {
			int xx = (x * 10 + i) % n;
			if (visit[xx]) continue;
			visit[xx] = true;
			p[xx] = x;
			num[xx] = i;
			q.push(xx);
		}
	}
	return false;
}
int main() {
	scanf("%d", &t);
	while (t-- && scanf("%d", &n)) {
		if (bfs()) print(0);
		else printf("BRAK");
		printf("\n");
	}
}