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

 

1. 사다리와 뱀을 만나면 무조건 이동한다.

2. 사다리와 뱀이 있는 칸은 여러 번 방문할 수도 있으니, 주사위 던진 횟수가 최소가 되게 신경써야 한다.

 

이 두 가지만 신경쓰면 크게 어렵지 않은 문제였다.

 

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

def bfs(start):
    q = deque()
    # 시작점을 큐에 넣고 방문체크
    q.append(start)
    visited[start] = True
    while q:
    	# 현재 위치를 cur에 저장
        cur = q.popleft()
        # 주사위를 굴려서 갈 수 있는 곳을 확인함
        for i in range(1,7):
            ncur = cur+i
            # 100번 칸에 도달했다면 주사위 던진 횟수를+1하고 탐색 종료
            if ncur==100:
                board[ncur]=board[cur]+1
                visited[ncur] = True
                return
            # 주사위를 던져서 간 곳이 보드를 넘어가지 않고
            # 아직 방문하지 않은 곳이라면
            if 0<ncur<=100 and not visited[ncur]:
            	# 방문체크 후 주사위 던진 횟수+1
                visited[ncur] = True
                board[ncur] = board[cur]+1
                
                # 사다리라면
                if ncur in ladder:
                	# 사다리의 도착점에 아직 방문하지 않았다면
                    # 방문체크하고 주사위 던진 횟수를 기록
                    if not visited[ladder[ncur]]:
                        visited[ladder[ncur]]=True
                        board[ladder[ncur]] = board[ncur]
                    # 이미 방문한 곳이라면
                    # 기존 횟수와 현재의 횟수 중 작은 것을 기록함
                    else:
                        board[ladder[ncur]]=min(board[ladder[ncur]], board[ncur])
                    # 무조건 사다리로 이동을 해야 하므로 큐에 사다리의 도착지를 추가함
                    q.append(ladder[ncur])
                
                # 뱀일 때에도 사다리일 때와 같은 방식으로 동작
                elif ncur in snake:
                    if not visited[snake[ncur]]:
                        visited[snake[ncur]]=True
                        board[snake[ncur]] = board[ncur]
                    else:
                        board[snake[ncur]]=min(board[snake[ncur]], board[ncur])
                    q.append(snake[ncur])
				# 평범한 칸일 때
                else:
                    q.append(ncur)
                

N,M = map(int,input().split())
board = [0]*101
visited= [False]*101
# 사다리와 뱀의 정보를 딕셔너리에 저장
# key:출발지 value:도착지
ladder = {}
snake = {}

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

# 1번 칸에서 탐색을 시작함
bfs(1)
# 100번 칸에 도달하는 데에 소요된 횟수를 출력
print(board[100])