[Python] 백준 16928번 '뱀과 사다리 게임' (DFS/BFS)

문제

16928번: 뱀과 사다리 게임

입력

• 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다.
• 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으로 이동한다는 의미이다.
• 다음 M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)가 주어진다. u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다.
• 1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다. 항상 100번 칸에 도착할 수 있는 입력만 주어진다.

출력

• 100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 출력한다.

문제 풀이

• x일 때 y로 이동, u일 때 v로 이동이므로 딕셔너리 형태로 사다리와 뱀의 위치 관리
• 이동횟수를 저장 할 board와 방문유무를 저장할 visited 배열을 따로 생성
• 목표 위치에 도달 했다면 이동횟수를 출력하고, 그렇지 않은 경우 사다리와 뱀이 있는경우 그리고 아무 것도 없는 경우를 구별하여 이동해야 한다
• 이동 하려는 위치가 범위 내에 있고 아직 방문되지 않은 경우 위 세 가지 경우를 나눠서 수행
• 뱀이나 사다리를 통해 이동을 마친 경우나, 아무 것도 없는 경우 방문처리하고, 보드 값을 이동횟수로 업데이트 한 후 큐에 다시 삽입
• 뱀과 사다리를 통해 이동하기 전의 위치는 방문처리 하지 않음 (뱀이나 사다리에 의해 틀린경로 출력 될 수 있기 때문에 ex) 뱀 "94 -> 90"인 경우 최소 경로가 "92 -> 98 ->  100"이나 94 -> 100으로 틀린 경로 탐색, 사다리도 마찬가지

코드

from collections import deque
n, m = map(int,input().split())
ladder = {}
snake = {}
board = [0] * 101
visited = [False] * 101
for _ in range(n):
    x, y = map(int,input().split())
    ladder[x] = y
for _ in range(m):
    u, v = map(int,input().split())
    snake[u] = v

queue = deque([1]) # 출발위치 삽입
while queue:
    x = queue.popleft()
    # 100에 도달했을 때 이동횟수 출력
    if x == 100:
        print(board[x])
        break

    for i in range(1, 7):
        nx = x + i
        # 이동할 위치가 범위 내에 있고, 아직 방문하지 않았을 때
        if nx <= 100 and not visited[nx]:
            # 사다리가 있는 경우
            if nx in ladder.keys():
                nx = ladder[nx]
            # 뱀이 있는 경우
            if nx in snake.keys():
                nx = snake[nx]
            # 아무것도 없는 경우와 사다리 뱀, 이동 마친 후
            if not visited[nx]:
                visited[nx] = True
                board[nx] = board[x] + 1
                queue.append(nx)

딕셔너리 자료형

02-5 딕셔너리 자료형