백준 #15558 점프 게임

코드

import sys
# sys.stdin = open('input.txt')
input = sys.stdin.readline
from collections import deque

def bfs(x, y):
    q = deque()
    q.append((x, y, 0))
    visited[x][y] = True

    while q:
        r, c, time = q.popleft()
        if c >= n:
            print(1)
            return

        if c + 1 < n + k:
            if not visited[r][c + 1] and arr[r][c + 1] and c + 1 > time:
                visited[r][c] = True
                q.append((r, c + 1, time + 1))

        if 0 <= c - 1:
            if not visited[r][c - 1] and arr[r][c - 1] and c - 1 > time:
                visited[r][c - 1] = True
                q.append((r, c - 1, time + 1))

        if c + k < n + k:
            if not visited[(r + 1) % 2][c + k] and arr[(r + 1) % 2][c + k] and c + k > time:
                visited[(r + 1) % 2][c + k] = True
                q.append(((r + 1) % 2, c + k, time + 1) )
    print(0)
    return


n, k = map(int, input().split())
arr = [list(map(int, input().rstrip())) + [2 for _ in range(k)] for _ in range(2)]

visited = [[False] * (n + k) for _ in range(2)]
bfs(0, 0)

풀이

BFS 문제이다. 시간마다 갈 수 있는 칸이 사라지기 때문에 time이란 변수로 체크해주었다.

배열 크기를 넘어서 점프를 해도 통과를 할 수 있기 때문에 마지막 index에서 최대 점프 거리만큼을 더해서 배열과 visited 크기를 늘려주었다.

오늘 좀 더 포스팅을 하고 싶은데 주말이라 놀고싶은 마음이….!!!