백준/Python) 16928 뱀과 사다리 게임 - BFS

💭 접근 방법

---

1. graph에 인덱스 저장 (현재 위치를 BFS에서 뽑아야하기 때문에 인덱스를 저장한다. graph는 이동할 곳 경로를 저장하는 용도이다.)
2. visited = [0] * 101 방문했는지 경로
3. BFS 시작
4. 초기 인덱스를 deque에 넣고 꺼내 주사위 + 1~6까지의 경로를 파악한다. 방문하지 않은 경로 인경우 visited[이전경로] + 1을 해준다.
5. 종료조건 : 앞으로 간 경로가 100인경우 종료한다.

코드로 보면 이해할수있습니다.

 

 

💡 결과

---

# 16928 뱀과사다리게임 G5
from collections import deque

N,M = map(int,input().split())
graph = [i for i in range(101)] #인덱스 현재 위치를 저장!
visited = [0] * 101
for _ in range(N+M):
    x,y = map(int,input().split())
    graph[x] = y #이동하는 곳의 인덱스 저장

def BFS(v):
    q = deque([v])
    visited[v] = 1

    while q:
        p = q.popleft() #현재인덱스

        for i in range(1,7):
            dice = p + i # 주사위
            if dice > 100:
                continue
            cnt = graph[dice] #주사위로 이동한 인덱스
            if visited[cnt] == 0: # 방문하지않았다면
                visited[cnt] = visited[p] + 1
                q.append(cnt)

                if cnt == 100:
                    return

BFS(1)
print(visited[100]-1)

 

 

 

💫 느낀점

---

정석적인 BFS로 접근하면 풀수 있는 문제이다. 다만 초기 graph설정에 값을 인덱스로 지정해줄 생각을 하지못해 헤맸던 문제이다.

 

 

 

 

16928번: 뱀과 사다리 게임