[백준/BOJ] - 16928번 python 풀이 - bfs

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

16928번: 뱀과 사다리 게임

---

1부터 시작하여 bfs로 주사위 수인 1~6 만큼 이동하여 100에 최소 횟수만큼 도달하려면?

 

처음 생각난 방법이 dp와 그래프 탐색이다.

그래프 탐색 방법 중 dfs를 사용하면 100에 도달하는 경우의 수가 여러개 나오는데 

그 많은 경우의 수 중 주사위 시도 횟수가 가장 작은 값을 구하기 위해 매번 비교를 해야한다.

 

하지만, bfs를 사용하여 방문하는 곳마다 방문처리를 하면 100에 도달하는 처음 경우가 가장 작은 

시도횟수일 것이다. dfs와는 다르게 비교의 필요성이 없다 판단하여 bfs를 채택했다.

 

스타트 포인트인 1을 queue에 넣고 반복문을 통해 1~6 범위 만큼 이동하여 사다리와 뱀의 여부를 확인.

계속 진행하며 조건을 만족하면 이동시키고 방문처리 한다. (이동 수 증가도)

그러다 맨 처음 100에 도달하는 경우가 곧 최소의 경우의 수가 되기 때문에( bfs 특성상 한번에 깊게 들어가는

 것이 아닌, 현재 시점에서 가능한 경우의 수를 모두 확인하며 진행.) 그렇기에 방문하는 곳 마다 방문처리를 해주면 

결국 cnt[100]에 있는 값은 최솟값이 도출.

 

---

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

def bfs():
    q = deque()
    q.append(1)
    ok[1] = 1
    while q:
        now = q.popleft() #기준점
        for i in range(1,7): #1~6
            next_move = now + i
            if next_move <= 100 and not ok[next_move]: #100 초과 -> break                
                if next_move in ladder.keys():
                    next_move = ladder[next_move]                            
                elif next_move in snake.keys():
                    next_move = snake[next_move]                                                                
                if ok[next_move] == 0:
                    q.append(next_move)
                    ok[next_move] = 1 #방문처리
                    cnt[next_move] = cnt[now] + 1
  
a,b = map(int,input().split())
ladder = dict()
snake = dict()
cnt = [0]*101 #칸마다 횟수 카운트
ok = [0]*101 #방문 횟수

for _ in range(a):
    i,j = map(int,input().split())
    ladder[i] = j
for _ in range(b):
    i,j = map(int,input().split())
    snake[i] = j
bfs()
print(cnt[100])

---