백준 8111번 0과 1

from collections import deque
t = int(input())

def bfs(n):
    u = 10 % n
    q = deque()
    q.append((1, 1))
    while q:
        x, mod = q.popleft()
        if x >= 10 ** 101:
            print('BRAK')
            return
        for y in [10 * x + 1, 10 * x]:
            if y % n == 0:
                print(y)
                return
            if y == 10 * x + 1:
                q.append((y, (mod * u + 1) % n))
            if y == 10 * x:
                q.append((y, (mod * u ) % n)) 
    
for _ in range(t):
    n = int(input())
    bfs(n) 

처음에는 이런식으로 단순하게 bfs 구현했다. 당연히 메모리 초과 나고 999 같은 큰 수는 계산되지도 않았다. 배열 대신 set도 써보고 했는데 모르겠었음. 대충 나머지에 대한 것은 접근했는데 구현까지 이어지지 않음.

from collections import deque

def bfs(n):
    check = [-1] * n
    how = [-1] * n
    afrom = [-1] * n
    
    q = deque()
    q.append(1 % n)
    check[1 % n] = 0
    how[1 % n] = 1
    while q:
        x = q.popleft()
        for y in [10 * x, (10 * x) + 1]:
            if check[y % n] == -1:
                if y == 10 * x:
                    how[y % n] = 0
                else:
                    how[y % n] = 1
                afrom[y % n] = x
                q.append(y % n)
                check[y % n] = check[x] + 1
                
    ans = []
    if check[0] == -1:
        print('BRAK')
    else:
        i = 0
        while i != -1:
            ans.append(how[i])
            i = afrom[i]
    print(*ans[::-1], sep = '')
    
t = int(input())

for _ in range(t):
    n = int(input())
    bfs(n)  

1. check, how, afrom 배열은 왜 크기가 n+1 인가? : 나머지 계산을 하기 때문에 탐색은 어차피 나머지(0 ~ n-1) 안에서 끝난다. n이 넘어가면 어차피 최소는 아니고 이미 이 전에 n의 배수 이미 나옴.
2. check[0] == -1 이면 n의 배수(나머지가 0이 되는) 것을 못 찾은 상태다
3. i == -1 이면 탐색끝. afrom 배열은 역으로 찾아 나가는 것이라서 역으로 출력해줘야한다.
4. check : 길이
   how: 1 또는 0
   afrom[i] : 0 또는 1을 붙이기 이전의 나머지 값

다른게 생각나면 추가..