15558_점프 게임

▶ 골드 5 (BFS)

풀이

길을 이동하는 방법은 1) 뒤로 가기 2) 앞으로 가기 3) 옆으로 가기

BFS를 통해서 갈 수 있는 모든 경로를 방문한 후, N칸이 넘어가면 성공으로 간주하고 1을 출력한 뒤 종료합니다.

갈 수 있는 경로의 조건은

1. 현재 시간 번째 칸 이상이고 (뒤로가는 경우만 해당)
2. 방문하지 않았고
3. 이동할 수 있는 칸인 경우

현재 칸이 N번 째 이상인 경우 종료.

고민한 점 

현재 칸에서 이동할 수 있는 3가지 칸에서는 동일한 시간을 가져야하는데,

처음에 visited를 숫자로 저장하여 time을 관리하려고 하니 칸을 이동할 때마다 시간이 증가했습니다.

그래서 queue에 [줄, 인덱스, 방문 시간] 형태로 방문 시간을 추가했습니다.

코드

# 15558 점프 게임
from collections import deque
import sys

input = sys.stdin.readline
n, k = map(int, input().split())
map = [input().strip() for _ in range(2)]


# BFS
queue = deque([(0, 0, 0)])
visited = [[False for _ in range(n)] for _ in range(2)]

while queue:
    row, idx, time = queue.popleft()

    routes = [[row, idx + 1], [row, idx - 1], [1 - row, idx + k]]
    for i in range(len(routes)):
        nextRow, nextIdx = routes[i]
        if nextIdx >= n:
            print(1)
            exit()
        if time < nextIdx and not visited[nextRow][nextIdx] and map[nextRow][nextIdx] == '1':
            visited[nextRow][nextIdx] = True
            queue.append([nextRow, nextIdx, time + 1])

print(0)