[baekjoon] 백준 16928번 : 뱀과 사다리 게임 (by python 파이썬) BFS

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

16928번: 뱀과 사다리 게임

 

정답 code

#뱀과 사다리 게임
from collections import deque
import sys
input = sys.stdin.readline

def bfs(v):
    queue = deque()
    queue.append(v)
    visit[v] = 1

    while queue:
        target = queue.popleft()

        for i in range(1,7):
            dice = target + i

            if dice > 100:
                continue
			
            #해당 인덱스에 적힌 수 추출(뱀이나 사다리가 있다면 이어진 수)
            cnt = bord[dice]
            #방문하지 않은 칸이면
            if visit[cnt] == 0:
                queue.append(cnt)
                #주사위 굴리기 전 칸까지 주사위 횟수 +1
                visit[cnt] = visit[target]+1

                if cnt == 100:
                    return


n, m = map(int,input().split())
bord = [i for i in range(101)]

for i in range(n+m):
    x,y = map(int,input().split())
    #사다리, 뱀 적용
    bord[x] = y

visit = [0] * 101

bfs(1)
print(visit[100]-1)

 

solution

처음엔 문제를 훨씬 어렵게 생각 했었다.

주어진 사다리를 이용해  최단기간으로 올라가는 길을 먼저 찾고 탐색을 하려했었다.

 

결국 그냥 단순히 1부터 bfs를 돌려 탐색하는 방법으로 풀었다.

1부터 주사위 1~6에대해 visit에 주사위 횟수를 저장해 간다.

 

사다리랑 뱀을 적용하기 위해 bord리스트 해당 인덱스 값을 변경해 사용 하였다.