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

2024년 8월 14일

문제 링크 : 백준 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을 출력한다.

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

 

문제 접근

 

문제의 핵심 포인트는 다음과 같다.

 

1. 시작점은 무조건 왼쪽 줄의 1번 칸이며, 해당 칸은 무조건 안전한 칸이다.

2. 유저는 매 초마다 아래의 세 가지 행동 중 하나를 해야 한다.
- 한 칸 앞으로 이동
- 한 칸 뒤로 이동
- 반대쪽 줄의 k칸 앞으로 이동

3. 매 초 마다 각 줄의 맨 앞 칸부터 한 칸씩 사라진다.

4. 클리어 조건은 어느 줄을 통해서이든 범위 밖으로 나가면 된다. 그런 경우 1을 출력하며, 어느 경로로든 클리어하지 못하면 0을 출력한다.

 

 

너비 우선 탐색 기법을 활용하여 시간이 1초 흐를 때마다 도달할 수 있는 모든 칸을 queue에 담을 것이며, 각 칸을 기준으로 다음으로 갈 수 있는 칸들을 next_v 배열에 담을 것이다.

특정 시간에 갈 수 있는 칸을 next_v에 담았다면 이를 그대로 queue에 옮겨담는 방식으로 각 시간마다 갈 수 있는 칸들을 구분짓기로 하였다.

 

이미 도달한 칸은 위험한 칸을 뜻하는 0으로 표시하여, 이미 도달한 칸 이후의 경로는 중복되므로 중복 연산을 막기 위해 도달할 수 없는 칸으로 방문표시를 대체하였다. 

 

또한 매 초마다 각 줄의 맨 앞 칸부터 한 칸씩 사라지므로, 이 또한 맨 앞 칸을 0으로 치환하는 방식으로 구현하였다. 

 

---

입력 예제

 

7 3
1110110
1011001

 

 

 

출력 예제

 

1

 

 

---

전체 코드

 

# 15558
from collections import deque

def bfs():
    queue = deque()
    queue.append([0, 0])

    time = 0
    next_v = []
    while queue:
        while queue:
            now_line, now_idx = queue.popleft()
            # 현재 라인의 인덱스 번호에서 반대편 라인으로 k 만큼 점프해서 보드 바깥으로 나갈 수 있으면 클리어 가능.
            # 이는 한 칸 전진해서 보드 바깥으로 나가는 클리어 조건을 넓게 포괄하기에 이 조건만으로 충분하다고 판단.
            if now_idx + k >= N:
                return 1
            # 뒤로 한 칸 갈 수 있는지
            if now_idx > 0 and board[now_line][now_idx - 1] == "1" and now_idx - 1 > time:
                next_v.append([now_line, now_idx - 1])
                board[now_line][now_idx - 1] = "0"
            # 앞으로 한 칸 갈 수 있는지
            if board[now_line][now_idx + 1] == "1":
                next_v.append([now_line, now_idx + 1])
                board[now_line][now_idx + 1] = "0"
            # 반대편 라인으로 k 만큼 점프할 수 있는지
            if board[(now_line + 1) % 2][now_idx + k] == "1":
                next_v.append([(now_line + 1) % 2, now_idx + k])
                board[(now_line + 1) % 2][now_idx + k] = "0"

        while next_v:
            queue.append(next_v.pop())

        # 보드의 시작점 부분을 위험한 땅으로 분류
        board[0][time], board[1][time] = "0", "0"
        time += 1

    # 끝까지 클리어하지 못하면 0 return
    return 0

if __name__ == "__main__":
    N, k = map(int, input().split())
    board = []
    board.append(list(input()))
    board.append(list(input()))

    print(bfs())

 

---

풀이 후기

 

너비 우선 탐색을 응용해 풀 수 있는 재밌는 문제였다.