[백준] 8111번 0과 1 ★★

💡문제접근

• 이전에 포스팅했던 [[백준] 9019번 DSLR]과 거의 비슷한 유형의 문제였다.
• N은 20000보다 작거나 같은 자연수이므로 방문 여부 배열의 크기를 20,000으로 잡아준다.
• 큐에 [현재 숫자, 만들어진 숫자(문자열 형태)] 형태로 넣어주면서 0 혹은 1을 하나씩 붙여나가면서 만들 수 있는 수가 N의 배수라면 현재 숫자를 리턴해주고 만약 만들어진 숫자의 길이가 100을 초과하면 "BRAK"를 리턴한다.

💡코드(메모리 : 34120KB, 시간 : 76ms)

from collections import deque
import sys
input = sys.stdin.readline

def BFS(N):
    queue = deque([(1, "1")])
    visited = [False] * 20001
    visited[1] = True

    while queue:
        current_num, current_str = queue.popleft()
        # 만약 만들어진 현재 숫자가 N의 배수라면?
        if current_num % N == 0:
            return current_str
        # 만약 구사과가 좋아하는 수의 길이가 100을 넘어선다면?
        if len(current_str) > 100:
            return "BRAK"
        # 1을 뒤에 붙이는 경우
        if not visited[((current_num * 10) + 1) % N]:
            visited[((current_num * 10) + 1) % N] = True
            queue.append([(((current_num * 10) + 1) % N), current_str + "1"])
        # 0을 뒤에 붙이는 경우
        if not visited[(current_num * 10) % N]:
            visited[(current_num * 10) % N] = True
            queue.append([((current_num * 10) % N), current_str + "0"])
    return "BRAK"

T = int(input())
for i in range(T):
    N = int(input().strip())
    print(BFS(N))

💡소요시간 : 2h