BOJ 점프게임 15558

작성일 | In

점프게임

  • 오른쪽 그림과 같은 지도가 있을 때 (N<=100,000)
  • 유저가 할 수 있는 행동은 3가지 중 하나
  • 한 칸 위로, 한 칸 아래로, 옆 칸으로(+k만큼 이동)
  • i초에 i번 칸이 사라진다

  • N번 칸을 넘어갈 수 있는지 구하는 문제

  • BFS는 단계별로 탐색이 진행 .
  • 단계적을 탐색이 진행되면 0초에 이동할 수 있는 거 시작점 밖에 없고

  • 1초에 이동하는고 다 이동, 2초에 이동하는거 다 이동하고 없어지고

  • i번 칸을 방문한 초 >=i 이면 방문할 수 있는 것이다.
from collections import deque
n,k = map(int,input().split())
a = [input() for _ in range(2)]
dirs = [(0,1),(0,-1),(1,k)]
dist = [[-1]*n for _ in range(2)]
q = deque()
q.append((0,0))
dist[0][0] = 0
ok = False
while q:
    x,y = q.popleft()
    for dx,dy in dirs:
        nx,ny = (x+dx)%2,y+dy
        if ny >= n:
            ok = True
            break
        if ny < 0:
            continue
        if dist[nx][ny] != -1:
            continue
        if a[nx][ny] == '0':
            continue
        if ny < dist[x][y] + 1: # 내가 가려고 하는 칸이 거리보다 작으면
            continue
        dist[nx][ny] = dist[x][y] + 1
        q.append((nx,ny))
    if ok:
        break
print(1 if ok else 0)

참고자료 codeplus

0%