👩‍💻🎄 [baekjoon] 15558번: 점프 게임

🖍️ solution

import sys
from collections import deque
from typing import List

def bfs(y: int, x: int):
    time, flag = -1, False
    q = deque([[y, x]])
    while q:
        for _ in range(len(q)):
            vy, vx = q.popleft()
            if vx+1 >= N or vx+K >= N:
                flag = True
                break
            if graph[vy][vx+1] and not visited[vy][vx+1]:  # 앞으로 한 칸 이동
                q.append([vy, vx+1])
                visited[vy][vx+1] = True

            if vx-1 > time+1 and graph[vy][vx-1] and not visited[vy][vx-1]:  # 뒤로 한 칸 이동, 갈 수 없는 구역을 미리 예상해서 풀어야 함
                q.append([vy, vx-1])
                visited[vy][vx-1] = True

            if graph[(vy+1) % 2][vx+K] and not visited[(vy+1) % 2][vx+K]:  # 앞으로 한 칸 이동
                q.append([(vy+1) % 2, vx+K])
                visited[(vy+1) % 2][vx+K] = True
        time += 1
    return flag

if __name__ == "__main__":
    N, K = map(int, sys.stdin.readline().split())
    graph = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(2)]
    visited = [[False] * N for _ in range(2)]
    print(1) if bfs(0, 0) else print(0)

💡 idea

• 매초마다 블럭 사라지는 기능 필요
  • 매초 단위로 큐입력을 끊기
  • while & for-loop는 초단위로 큐입력 끊어내는 구현하기 매우 어려움
  • 일반적인 bfs 구현체 대신 if-else 구문으로 큐 하나에 대한 모든 경우의 수가 한 번에 처리 되도록 구현
  • 뒤로 가능 경우에 대해서만 예외처리 - 시간 초마다 블럭을 삭제하는 방법 X, 뒤로 가려는 블럭이 다음번에 삭제 예정인지 판단 - 사라질 예정이면 큐에 삽입하지 않고 pass