[BOJ/백준] 백준 8111 0과 1 파이썬

문제 링크 : https://www.acmicpc.net/problem/8111

8111번: 0과 1

경우의 수가 2^100이기 때문에 단순히 BFS만으로는 절대 불가능하기 때문에 가지치기가 중요하다.

나는 도저히 방법이 떠오르지가 않아서 핵심 알고리즘들을 좀 찾아봤다.

그래서 찾은게 모듈러 연산을 통해서 하는 것이다

a%b = c 일때 d는 임의의 아무숫자이고 c 끝에 d를 붙인 숫자를 b로 모듈러 연산한 값을 e라 하고 a 끝에 d를 붙인 숫자를 b로 모듈러 연산한 값을 f라 하면 e와 f의 결과 값은 같다. 예를들어 2479%7 = 1 일때 9를 끝에 붙인다고 하면 19와 24799가 되고 각각을 다시 7로 모듈러 연산하면 같다. 19%7 =  5 24799%7 = 5

이 알고리즘 되로 하면 0~n-1의 숫자들 가지고 놀기 때문에 얼마 걸리지 않는다.

BFS는 1부터 넣고 시작하고 visited 배열의 경우 0번째는 원래 몫, 1번째는 tc 번호로 tc마다 구별하려고 넣었다.

from sys import stdin
from collections import deque

input = stdin.readline

tc = int(input())
visited =[['',0] for _ in range(20001)]
visited_num = 0

def solv():
    n = input()
    if n.count('1')+n.count('0') == len(n):
        print(0)
        return
    else:
        n = int(n)
        bfs(n)
def bfs(n):
    global visited
    q = deque([1])
    visited[1] = ['1', visited_num]

    while q:
        now = q.pop()

        if len(visited[now][0]) == 100:
            print('BRAK')
            return

        for num in [0,1]:
            nxt = (now*10+num)%n
            if nxt != 0:
                if visited[nxt][1] != visited_num:
                    visited[nxt] = [visited[now][0]+str(num),visited_num]
                    q.appendleft(nxt)
            else:
                print(visited[now][0]+str(num))
                return
for _ in range(tc):
    visited_num += 1
    solv()