[Python] 16928번 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

---

 

22/11/30

 

 

클래스에 못 푼 문제가 있길래 푼 문제이다.

 

전형적인 BFS문제이지만, 약간의 변형이 필요한 문제로, 그 상황만 잘 처리를 해준다면 쉽게 AC를 받을 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

처음에 이 문제를 보고 뱀과 사다리를 타는 것이 의무적으로 타는 것이 아닌, 선택적으로 탈 수 있는 것인 줄 알고 의문의 WA를 많이 받았었다.

 

예를 들어, 3번 칸에 94번으로 갈 수 있는 사다리가 있으면, 3번 칸은 방문처리를 하면 안된다.

 

왜냐하면, 3번 칸에 도착하자마자 사다리를 타고 94번으로 직행하기 때문이다.

 

사다리나 뱀을 타는 행위는, 만약 그 칸에 뱀이나 사다리가 있으면 무조건적으로 타야 하는 것이기 때문에, 실질적으로 3번 칸에 내가 멈춰있을 수 없다.

 

 

따라서, 두 가지 경우로 나뉜다.

 

1. 내가 있는 칸에 뱀이나 사다리가 있는 경우

 

이 경우에는 의무적으로 뱀이나 사다리를 타야 하므로, 내가 그 칸에 실질적으로 머무를 수 없다. 따라서, 내가 있는 칸을 방문처리를 하지 않고 뱀이나 사다리를 타고 간 칸을 방문 처리해준다. 그리고 그 칸을 큐에 넣는다.

 

 

2. 내가 있는 칸에 뱀이나 사다리가 없는 경우

 

이 경우에는 실질적으로 머무를 수 있으므로, 내가 있는 칸을 방문처리해주고 큐에 넣는다.

 

 

이 점만 일반적인 BFS문제와 다르고, 나머지는 그냥 BFS 하듯 똑같이 하면 된다.

 

나 같은 경우, 뱀과 사다리를 그래프에 간선 집어넣듯, 101칸짜리 이차원 배열을 선언하여 뱀과 사다리를 집어넣어 주었다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 16928번 뱀과 사다리 게임
# 그래프 이론, 그래프 탐색, BFS
import sys
from collections import deque
input = sys.stdin.readline

ladder_and_snake = [[] for _ in range(101)]  # 뱀과 사다리를 저장하는 배열
visited = [0 for _ in range(101)]  # 방문 여부 배열
N, M = map(int, input().rstrip().split())  # 사다리의 수, 뱀의 수

for _ in range(N):  # 사다리의 정보 입력
    start, end = map(int, input().rstrip().split())
    ladder_and_snake[start].append(end)

for _ in range(M):  # 뱀의 정보 입력
    start, end = map(int, input().rstrip().split())
    ladder_and_snake[start].append(end)

queue = deque()
queue.append((1, 0))  # 시작위치, 주사위를 굴리는 횟수
visited[1] = 1

while queue:
    now_pos, time = queue.popleft()
    if now_pos == 100:
        print(time)
        break
    for i in range(1, 7):
        next_pos = now_pos + i
        if 1 <= next_pos <= 100 and visited[next_pos] == 0:
            if ladder_and_snake[next_pos]:  # 사다리나 뱀이 있으면 그 칸은 지나치고 무조건 사다리나 뱀을 타야
                next_pos_2 = ladder_and_snake[next_pos][0]
                visited[next_pos_2] = 1
                queue.append((next_pos_2, time+1))
            else:
                visited[next_pos] = 1
                queue.append((next_pos, time+1))