백준: 15558 점프 게임

문제

15558번: 점프 게임

 

문제 풀이

 지도가 좌측, 우측 2개의 줄로 나뉘어 있고, 3가지의 경우로 현재 칸에서 이동할 수 있다. 첫 번째는 현재 칸에서 한 칸 앞으로 가는 것이고 두 번째는 한 칸 뒤로 가는 것이다. 마지막으로 다른 줄에서 K칸 앞으로 가는 경우가 있다. 문제를 풀기 위해서는 앞서 다룬 토마토 문제와 같이, 한 단계에서 처리 가능한 모든 경우의 수를 처리해주어야 한다.

 

 토마토 문제와 달리 다음번 칸으로 갈 수 있는지와, 1초가 지나면 이전에 앞에서부터 한 칸씩 사라진다. 따라서 다음에 방문 가능한 칸의 범위를 `0 <= y < n`이 아닌,  현재 `인덱스 < y < n`과 같이 진행해주어야 한다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y, idx):
    return idx < y < n and game_map[x][y] and not visited[x][y]


def bfs(start):
    q = deque([start])
    cur_idx = 0
    while q:
        for _ in range(len(q)):
            x, y = q.popleft()
            for next_x, next_y in ((x, y + 1), (x, y - 1), (~x, y + k)):
                if next_y >= n:
                    return 1
                if visitable(next_x, next_y, cur_idx):
                    q.append((next_x, next_y))
                    visited[next_x][next_y] = True
        cur_idx += 1
    return 0


if __name__ == "__main__":
    LEFT, RIGHT = 0, 1
    n, k = map(int, (stdin.readline().split()))
    game_map = [list(map(int, stdin.readline().strip())) for _ in range(2)]
    visited = [[False] * n for _ in range(2)]
    print(bfs([0, 0]))

 현재 칸에서 방문할 수 있는 3가지 경우의 수를 `(x, y + 1)`, `(x, y - 1)`, `(~x, y + k)`로 표현하였다. 또한 앞의 칸이 사라지는 것을 반영하기 위해 y의 범위에 현재 인덱스를 반영하였다.