[Algorithm] BaekJoon : 15558. 점프 게임 by Python

[문제 바로가기] https://www.acmicpc.net/problem/15558

📌문제 설명

상근이는 아래 그림과 같은 지도에서 진행하는 게임을 만들었다.

지도는 총 2개의 줄로 나누어져 있으며, 각 줄은 N개의 칸으로 나누어져 있다. 칸은 위험한 칸과 안전한 칸으로 나누어져 있고, 안전한 칸은 유저가 이동할 수 있는 칸, 위험한 칸은 이동할 수 없는 칸이다.

가장 처음에 유저는 왼쪽 줄의 1번 칸 위에 서 있으며, 매 초마다 아래 세 가지 행동중 하나를 해야 한다.

• 한 칸 앞으로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i+1번 칸으로 이동한다.
• 한 칸 뒤로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i-1번 칸으로 이동한다.
• 반대편 줄로 점프한다. 이때, 원래 있던 칸보다 k칸 앞의 칸으로 이동해야 한다. 예를 들어, 현재 있는 칸이 왼쪽 줄의 i번 칸이면, 오른쪽 줄의 i+k번 칸으로 이동해야 한다.

N번 칸보다 더 큰 칸으로 이동하는 경우에는 게임을 클리어한 것이다.

게임을 재밌게 하기 위해서, 상근이는 1초에 한 칸씩 각 줄의 첫 칸이 사라지는 기능을 만들었다. 즉, 게임을 시작한지 1초가 지나면 1번 칸이 사라지고, 2초가 지나면 2번 칸이 사라진다. 편의상 유저가 먼저 움직이고, 칸이 사라진다고 가정한다. 즉, 이번에 없어질 칸이 3번 칸인데, 상근이가 3번 칸에 있다면, 3번 칸에서 다른 칸으로 이동하고 나서 3번 칸이 없어지는 것이다.

각 칸의 정보가 주어졌을 때, 게임을 클리어 할 수 있는지, 없는지 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N과 k가 주어진다. (1 ≤ N, k ≤ 100,000)

둘째 줄에는 왼쪽 줄의 정보가 주어진다. i번째 문자가 0인 경우에는 위험한 칸이고, 1인 경우에는 안전한 칸이다. 셋째 줄에는 오른쪽 줄의 정보가 주어지고, 각 문자의 의미는 왼쪽 줄의 의미와 동일하다.

왼쪽 줄의 1번 칸은 항상 안전한 칸이다.

출력
게임을 클리어할 수 있으면 1을, 없으면 0을 출력한다.

---

💡 문제 풀이

BFS를 이용하여 유저가 이동할 수 있는 3가지 행동을 그대로 구현하면 된다.
이동시 도착지점의 값이 '1'(이동할 수 있는 칸)인지 확인하며 이동한다.

이 때, 1초에 한 칸씩 각 줄의 첫 칸이 줄어들기 때문에 '한 칸 뒤로 이동'의 경우 사라지는 칸에 주의한다.

이동하려는 왼쪽 줄, 오른쪽 줄의 칸을 방문했는지 표시하며 중복방문을 피하고, 이동한 칸이 N보다 큰(인덱스는 0부터 시작이므로) 상황이 발생하면 '게임 클리어'다.

만약, BFS 탐색이 종료 될 때 까지 게임을 클리어하지 못하면 0을 출력한다.

코드는 다음과 같다.

import sys
from collections import deque
sys.stdin = open('백준15558. 점프 게임.txt', 'r')
N, k = map(int, input().split())
lines = [sys.stdin.readline().rstrip() for _ in range(2)]
queue = deque([(0, 0)])
visited = [[0]*N for _ in range(2)]
time = -1
flag = False
while queue:
    for _ in range(len(queue)):
        d, idx = queue.popleft()
        # 게임 클리어
        if idx+1 >= N or idx+k >= N: 
            flag = True
            break
        # 한 칸 앞으로 이동
        if int(lines[d][idx+1]) and not visited[d][idx+1]: 
            queue.append((d, idx+1))
            visited[d][idx+1] = 1
        # 한 칸 뒤로 이동
        if idx-1 > time+1 and int(lines[d][idx-1]) and not visited[d][idx-1]: 
            queue.append((d, idx-1))
            visited[d][idx-1] = 1
        # 반대편 줄 & k칸 앞으로 이동
        if int(lines[(d+1)%2][idx+k]) and not visited[0][idx+k]: 
            queue.append(((d+1)%2, idx+k))
            visited[(d+1)%2][idx+k] = 1
    time += 1
print(1) if flag else print(0)

---