[Python/파이썬] 백준 15558번 점프 게임

https://www.acmicpc.net/problem/15558

 

코드

from collections import deque

n, k = map(int, input().split())
game_map = []
for _ in range(2):
    game_map.append("0"+input())

q = deque([(0, 1, 1)])
visited = [[False]*(n+1) for _ in range(2)]
visited[0][1] = True
while q:
    line, num, sec = q.popleft()
    for nx_line, nx_num in [(line, num+1), (line, num-1), (line ^ 1, num+k)]:
        if nx_num > n:
            print(1)
            exit()
        if 0 <= nx_num <= n and game_map[nx_line][nx_num] == "1" and nx_num > sec and not visited[nx_line][nx_num]:
            q.append((nx_line, nx_num, sec+1))
            visited[nx_line][nx_num] = True
print(0)

 

왼쪽 줄이든, 오른쪽 줄이든 상관없이 N번 칸보다 더 큰 칸으로 이동할 수 있는지만 확인하면 되는 문제였다. 

 

1. 우선 입력받은 게임 지도 데이터는 `game_map`에 저장해놓는다. 0번째 행이 왼쪽 줄, 1번째 행이 오른쪽 줄이다. 각 줄에는 앞에 "0"을 임의로 추가하여 1번 칸이 1번 인덱스에서 시작할 수 있도록 했다.

2. BFS:

  2-1. deque에 첫 칸을 넣는다. `(0, 1, 1)` 형식으로 넣는데, 앞에서부터 줄, 칸, 시간을 의미한다. 줄은 0이 왼쪽 줄이고, 1이 오른쪽 줄이다.

  2-2. 방문 처리를 위한 `visited` 배열을 만들고, 첫번째 칸을 방문처리한다.

  2-3. q의 앞에서부터 하나의 원소를 뽑아서 이동할 수 있는 칸을 찾는다. 후보가 되는 칸은 같은 라인에서 +1칸, 같은 라인에서 -1칸, 옆줄의 현재+k칸이다.

  2-4. 만약 후보칸이 N칸을 넘어서는 칸이라면 1을 출력하고 프로그램을 종료한다. 그렇지 않다면 가능한 칸은 q에 넣고, 방문 처리를 한다.