[백준][Python][15558][BFS] 점프 게임

문제 : https://www.acmicpc.net/problem/15558

15558번: 점프 게임

BFS 문제다.

 

현재 위치를 x, 현재 줄을 line, 현재 시간을 time이라 할 때, 큐에 각각 [(line+1) %2, x + (k, 1, -1), time+1]을 넣어준다.

이때,  ( (line+1) %2, x + (k, 1, -1) ) 에 대해 이미 탐색한 곳인지를 확인해야 한다.

또한, 새로운 위치가 N을 넘었는지, 그리고 지워진 칸에 있는지를 확인해야 한다.

 

특별히 복잡한 코드가 아니라서 코드로 보는게 더 좋다.

import sys
from collections import deque

n, k = [int(i) for i in sys.stdin.readline().split()]

d = []
v = dict()
for _ in range(2):
    d.append([int(i) for i in sys.stdin.readline().strip()])


q = deque()
q.append([0, 0, -1])
v[(0, 0)] = True

while q:
    line, x, time = q.popleft()


    # x+k
    newl, newx = (line+1)%2, x + k

    if newx >=n:
        print(1)
        sys.exit()
    if x <=time:
        continue
    if (newl,newx) not in v and d[newl][newx] ==1:
        q.append([newl, newx, time+1])
        v[(newl,newx)] = True

    # x+1
    newl, newx = line, x + 1
    if newx >=n:
        print(1)
        sys.exit()
    if x <=time:
        continue
    if (newl,newx) not in v and d[newl][newx] ==1:
        q.append([newl, newx, time+1])
        v[(newl,newx)] = True
    # x-1

    newl, newx = line, x - 1
    if newx >=n:
        print(1)
        sys.exit()

    if x <=time:
        continue

    if (newl,newx) not in v and d[newl][newx] ==1:
        q.append([newl, newx, time+1])
        v[(newl,newx)] = True

print(0)