[BFS] 백준 16928번 : 뱀과 사다리 게임 - 파이썬 Python

 

 

생각하기

최소의 횟수로 주사위를 던지기 위해서는 BFS 알고리즘이 딱이었다.

가장 근처에 있는 아이들을 먼저 검사하면서 100에 딱 갔을때 바로 종료시켜버리면 그 때가 최소 주사위 던진 횟수일 것이다

 

잠시 BFS에 대해 정리하기

큐를 이용하여 한 정점에서 시작해서 모든 정점을 방문하는 알고리즘

단계별로 주변 노드들을 넣어가며 진행하기 때문에 최단거리 알고리즘에 적합

어떤 문제가 그래프로 변환이 가능하고 모든 가중치가 1인 경우에는 BFS로 간주 

큐에 넣을 때 해당 노드 방문 표시하는 것이 중요!!

1. 시작 정점 큐에 넣어주기
2. 큐에 요소가 존재하는 한 무한반복하는 while문 안에서 큐의 요소를 하나 뺀다
3. 큐에 연결된 요소들중 방문하지 않은 항목들을 다시 큐에 넣음

구현하기

뱀과 사다리가  규칙상으로는 다르지만 사실 어디로 이동한다는 측면에서 똑같다

따라서 box 배열은 아래와 같이 짤 수 있다

• 해당 칸이 일반 이면 0
• 해당 칸이 뱀이나 사다리인 경우 -> 이동할 칸 idx

visited 배열을 선언해서 방문한 칸은 다시 방문하지 않도록 한다

 

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

N, M = map(int, input().split())

box = [0] * 101

for _ in range(N+M):
    start, dest = map(int, input().split())
    box[start] = dest

q = deque()

visited = [False]*101

# 큐에 들어갈 튜플 (위치, 횟수)

q.append((1,0))
visited[1] = True

while len(q) != 0:
    
    cur_pos_cnt = q.popleft()
    if cur_pos_cnt[0] == 100:
        print(cur_pos_cnt[1])
        break


    for dice in range(1, 7):
        moved_pos = cur_pos_cnt[0] + dice

        if moved_pos > 100:
            continue
        else:
            if visited[moved_pos] == True:
                continue
            else :
                visited[moved_pos] = True
                if box[moved_pos] != 0:
                    q.append((box[moved_pos], cur_pos_cnt[1]+1))
                else:        
                    q.append((moved_pos, cur_pos_cnt[1]+1))