[탐색/BFS] 백준 16928 뱀과 사다리 게임 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

16928번: 뱀과 사다리 게임

 

 

 

2. 문제 풀이

 뱀과 사다리 게임에서 100번째 칸에 도착하는 최소 횟수를 구하는 문제입니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 BFS 탐색을 통해서 구할 수 있습니다. 보드판은 10*10 크기이지만, 어차피 앞으로만 진행하기 때문에 1차원 리스트를 써도 무방합니다.

 

 

 

3. 코드

import sys
from collections import deque
input = sys.stdin.readline

#입력
board = [0]*101 #보드판
N, M = map(int, input().split())
ladder = {} #사다리
for _ in range(N):
    x, y = map(int, input().split())
    ladder[x] = y #사다리 저장

snake = [] #뱀
for _ in range(M):
    u, v = map(int, input().split())
    snake.append(u) #뱀은 위치만 저장

#bfs탐색
visited = [False]*101 #방문여부
queue = deque([1]) #1번 칸부터 시작
visited[1] = True
while queue:
    #주사위는 1~6
    x = queue.popleft()
    for i in range(1, 7):
        nx = x+i
        #범위를 초과하거나 이미 방문했거나 뱀이면 무시
        if nx > 100 or visited[nx] or nx in snake:
            continue
        #사다리일 경우 해당 칸으로 이동
        if nx in ladder.keys():
            nx = ladder[nx]
        #첫 방문일 경우
        if not visited[nx]:
            queue.append(nx)
            visited[nx] = True
            board[nx] += board[x]+1
print(board[100])

 뱀 칸에 가는 건 무조건 손해이기 때문에, 아예 제외하고 코드를 짰습니다. 하지만... 간과한 게 있었죠. 사다리로 이동했을 때의 칸이 뱀일 경우입니다. 따라서 위 코드는 틀린 코드입니다.

 

 

import sys
from collections import deque
input = sys.stdin.readline

#입력
board = [0]*101 #보드판
N, M = map(int, input().split())
ladder = {} #사다리
for _ in range(N):
    x, y = map(int, input().split())
    ladder[x] = y #사다리 저장

snake = {} #뱀
for _ in range(M):
    u, v = map(int, input().split())
    snake[u] = v #뱀 저장

#bfs탐색
visited = [False]*101 #방문여부
queue = deque([1]) #1번 칸부터 시작
visited[1] = True
while queue:
    #주사위는 1~6
    x = queue.popleft()
    for i in range(1, 7):
        nx = x+i
        #범위를 초과하거나 이미 방문했으면 무시
        if nx > 100 or visited[nx]:
            continue
        #사다리일 경우 해당 칸으로 이동
        if nx in ladder.keys():
            nx = ladder[nx]
        #뱀일 경우 해당 칸으로 이동
        if nx in snake.keys():
            nx = snake[nx]
        #첫 방문일 경우
        if not visited[nx]:
            queue.append(nx)
            visited[nx] = True
            board[nx] += board[x]+1
print(board[100])

  뱀일 경우 이동하는 코드도 추가해야 통과됩니다. BFS 탐색에 대한 코드는 2. 문제풀이의 링크를 참조해주세요.