[백준 16928번] 뱀과 사다리 게임 - 파이썬

문제 링크:

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

16928번: 뱀과 사다리 게임

 

---

풀이 유형:

그래프 이론, 그래프 탐색, 너비 우선 탐색

 

풀이 과정:

이 문제는 앞서 풀은 이모티콘 문제와 유사하다. 이모티콘 문제는 다음 포스트를 참고하자.

https://data-flower.tistory.com/80

[백준 14226번] 이모티콘 - 파이썬

 

여기서 사다리와 뱀을 딕셔너리로 받는다는 점이 이모티콘에서의 클립보드를 받는 점과 매우 유사하다.

너비 우선 탐색(bfs)을 이용해 큐에서 하나씩 원소를 꺼내어 확인해주면 된다.

 

이 문제는 다음 조건들을 고려해야 한다.

1. 이동하는 위치(next_place)에 사다리가 있다면, 이동하는 위치(next_place)가 사다리를 타고 올라가야 한다는 점
2. 이동하는 위치(next_place)에 뱀이 있다면, 이동하는 위치(next_place)가 뱀을 타고 내려와야 한다는 점
3. 이동하는 위치에(next_place)에 아무것도 없다면, 해당 위치를 방문 표시 및 주사위 굴린 횟수를 1개 추가해야 한다는 점

 

조건을 이해했다면, 이제 뱀과 사다리 게임 문제를 풀어보자.

 

풀이 코드:

# 16928 뱀과 사다리 게임

from collections import deque

# 사다리의 수, 뱀의 수 입력받기
n, m = map(int, input().split())

# 1부터 100번째 칸 방문횟수
board = [0] * 101
# 맵 방문표시
visited = [False] * 101

# 사다리, 뱀 딕셔너리 선언
ladder = dict()
snake = dict()
# 사다리 정보 입력받기
for _ in range(n):
    a, b = map(int, input().split())
    ladder[a] = b
# 뱀 정보 입력받기
for _ in range(m):
    a, b = map(int, input().split())
    snake[a] = b


# 큐 구현
q = deque([1])

# 큐가 빌 때까지 반복
while q:
    x = q.popleft()
    # 100번 칸에 도착했다면
    if x == 100:
        # 주사위 굴린 횟수 출력
        print(board[x])
        # 반복문 탈출
        break
    # 주사위에 있는 1부터 6까지 차례대로 입력받아
    for dice in range(1, 7):
        # 다음으로 이동할 위치 보기
        next_place = x + dice
        # 맵을 벗어나지 않거나 아직 방문하지 않은 칸이라면
        if next_place <= 100 and not visited[next_place]:
            # 이동할 위치에 사다리가 있다면
            if next_place in ladder.keys():
                next_place = ladder[next_place]
            # 이동할 위치에 뱀이 있다면
            if next_place in snake.keys():
                next_place = snake[next_place]
            # 이동할 위치에 아무것도 없다면
            if not visited[next_place]:
                # 방문 표시
                visited[next_place] = True
                # 주사위 굴린 횟수 추가
                board[next_place] = board[x] + 1
                # 큐에 이동한 위치 삽입
                q.append(next_place)

 

 

16928 뱀과 사다리 게임