백준 15558 파이썬 python : 점프 게임 @@황소처럼 우직하게@@ 이거이거 BFS 큐 두개로 푸는것이여!

간단간단하다구

원래 기본 BFS는 큐 한개로 구현이 되지.

이거는 시간을 고려해줘야 하기 때문에, (매초마다 1칸씩 없어지는) 큐 두개로 시간과 동기화 시켜줘야 해 ^^

아래는 흔히 틀리는 반례야 (djm03178 님이 등록해주셨어)

23 5
10000000100010010000000
00011111001111111100100

n, k = map(int, input().split())
lst1 = input()
lst2 = input()
lst = [lst1, lst2]
visited = [[0 for i in range(n)] for _ in range(2)]
visited[0][0] = 1

def bfs():
    q = []
    q2 = []
    q2.append([0, 0])
    remove = 0
    while q2:
        now_idx, lst_num = q2.pop(0)
        # print("now_idx %d, lst_num %d" % (now_idx, lst_num))
        if now_idx + 1 >= n or now_idx + k >= n:
            return 1
        if lst[lst_num][now_idx + 1] == '1' and visited[lst_num][now_idx + 1] == 0:
            visited[lst_num][now_idx + 1] = 1
            q.append([now_idx + 1, lst_num])
        if now_idx - 1 > remove and lst[lst_num][now_idx - 1] == '1' and visited[lst_num][now_idx - 1] == 0:
            visited[lst_num][now_idx - 1] = 1
            q.append([now_idx - 1, lst_num])
        if lst[(lst_num + 1) % 2][now_idx + k] == '1' and visited[(lst_num + 1) % 2][now_idx + k] == 0:
            visited[(lst_num + 1) % 2][now_idx + k] = 1
            q.append([now_idx + k, (lst_num + 1) % 2])
        if not q2:
            q2 = q
            q = []
            remove += 1
    return 0

print(1 if bfs() else 0)