백준_16928_뱀과 사다리 게임(python)

※ 접근법

 먼저 입력 제한이 n,m의 크기와 보드판의 크기가 크지 않았기 때문에 그래프 탐색을 제일 먼저 떠올렸고 주사위를 한 번 굴렸을 때 주사위 숫자 안에 있는 것들을 먼저 방문해야 하니 가까운 노드부터 먼저 탐색하는 bfs로 풀어보기로 했다.

 

※ 풀이

 1. 사다리와 뱀에는 차이가 있지만 결국 시작지점과 끝지점이 있는 포탈이라고 생각했다.

 2. visited의 크기를 108로 넉넉하게 설정해줬다. 보드판은 100까지 밖에 없지만 끝나는 조건이 100을 넘어가면이기 때문에 IndexError를 일으키지 않기 위해서다.

 3. 시작지점부터 주사위를 굴리고 주사위를 굴려 이동한 곳에 사디리 또는 뱀이 있다면 거기로 이동하고 원래 있던 곳 + 1을 해준다.

 4. 이동한 곳이 100보다 크거나 같았다면 바로 리턴해준다.

 

from collections import deque

n,m = map(int,input().split())

start = []
end = []
for i in range(n+m):
    x,y = map(int,input().split())
    start.append(x)
    end.append(y)

dx = [1,2,3,4,5,6]

def bfs(s,visited):
    q = deque()
    q.append(s)
    visited[s] = 0
    while q:
        x = q.popleft()
        for i in range(6):
            nx = x + dx[i] 
            if visited[nx] == -1:# 방문한 적이 한 번도 없으면서
                visited[nx] = visited[x] + 1
                if nx >= 100:
                    return visited[nx]
                if nx in start:
                    number = end[start.index(nx)]
                    if visited[number] == -1:
                        visited[number] = visited[x] + 1
                        q.append(number)
                else:
                    q.append(nx)

visited = [-1] * 108
print(bfs(1,visited))

※ 회고 

 사다리와 뱀을 만났다면 무조건 이동했어야 했다. bfs 함수에서 마지막 else구문을 추가해서 사다라나 뱀을 만나지 않은 경우 즉, 주사위를 굴려서 도착한 경우에만 q에 추가한다. 사다리와 뱀을 만났을 경우에는 무조건 이동해야하니 이동한 칸만 q에 추가해야 하는 것이다.