백준[Python] - 16928 : 뱀과 사다리 게임

문제

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

16928번: 뱀과 사다리 게임

 

풀이

특정 위치까지의 최단거리를 구하는 문제이다.

BFS를 활용한 방식으로 각 위치에서의 거리를 구해나갈 수 있으며, 위 문제에서는 뱀과 사다리라는 특정 조건이 존재하기 때문에
해당 경우를 고려해야하므로 일반적인 거리 구하기 문제보다는 더 까다로운 문제였다고 생각한다.

고려 사항

뱀과 사다리의 출발점에 속하는 위치에 도달하게 되면 반드시 이를 따라 움직여야 한다.

 

그러므로, 해당 위치에서는 주사위를 굴려 도달할 수 있는 +1~6까지의 범위에 대해 고려할 필요가 없고, 고려해서도 안된다. 다만, 뱀과 사다리를 따라 움직일 뿐이다.

 

따라서, 뱀이나 사다리의 출발점에 위치하는지 여부를 먼저 따지고 그 후에 +1~6까지의 진행 방식을 따르면 해결 가능하다.

나의 풀이

# 뱀과 사다리 게임
import sys
from collections import deque
input = sys.stdin.readline
board = [[j+i*10 for j in range(1,11)] for i in range(10)]
distance = [[0]*10 for _ in range(10)]
n,m = map(int, input().strip().split())
ladder, snake = dict(), dict()
for _ in range(n):
    a,b = map(int, input().strip().split())
    ladder[a] = b
for _ in range(m):
    a,b = map(int, input().strip().split())
    snake[a] = b
# bfs
start = (0,0)
q = deque()
q.append(start)
dist=1
distance[0][0]=-1
def bfs():
    new_q = deque()
    num_q = deque()
    while q:
        x,y = q.popleft()
        for i in range(7):
            if (y+i)<=9:
                if distance[x][y+i]==0:
                    distance[x][y+i]=dist
                    if board[x][y+i] in ladder.keys():
                        r = (ladder[board[x][y+i]]-1)//10
                        c = (ladder[board[x][y+i]]-1)%10
                        if distance[r][c]==0:
                            distance[r][c]=dist
                            new_q.append((r,c))
                            num_q.append(board[r][c])
                    elif board[x][y+i] in snake.keys():
                        r = (snake[board[x][y+i]]-1)//10
                        c = (snake[board[x][y+i]]-1)%10
                        if distance[r][c]==0:
                            distance[r][c]=dist
                            new_q.append((r,c))
                            num_q.append(board[r][c])
                    else:
                        new_q.append((x,y+i))
                        num_q.append(board[x][y+i])

            else:
                if x<9:
                    new_x = x+1
                    new_y = y+i-10
                else:
                    if y+i>9:
                        break
                if distance[new_x][new_y]==0:
                    distance[new_x][new_y]=dist
                    if board[new_x][new_y] in ladder.keys():
                        r = (ladder[board[new_x][new_y]]-1)//10
                        c = (ladder[board[new_x][new_y]]-1)%10
                        if distance[r][c]==0:
                            distance[r][c]=dist
                            new_q.append((r,c))
                            num_q.append(board[r][c])
                    elif board[new_x][new_y] in snake.keys():
                        r = (snake[board[new_x][new_y]]-1)//10
                        c = (snake[board[new_x][new_y]]-1)%10
                        if distance[r][c]==0:
                            distance[r][c]=dist
                            new_q.append((r,c))
                            num_q.append(board[r][c])
                    else:
                        new_q.append((new_x,new_y))
                        num_q.append(board[new_x][new_y])

    return new_q
while q:
    q = bfs()
    dist+=1
print(distance[9][9])