[n16928] 뱀과 사다리 게임

---

[처음 든 생각]

최소를 구하라고 해서 bfs가 제일 먼저 떠올랐다.

근데 bfs 구현을 매끄럽게 잘 해내지 못하는 상태라

사전공부를 하고 왔다.

 

사다리와 뱀이 이 문제에서는 키포인트!

너비 우선 탐색은 현재 노드에서 갈 수 있는 모든 노드를 먼저 탐색하는 과정이기 때문에,

최단 거리 구할 때 주로 사용한다.

 

https://eboong.tistory.com/253

[이것이 코딩테스트다 Ch5 ] DFS와 BFS

bfs에서는 큐를 사용한다. 

 

** Bfs 동작 방식 **

1. 탐색 시작 노드를 큐에 삽입하고 방문처리

2. 큐에서 노드를 꺼낸 후 (popleft()), 해당 노드의 인접 노드 중에서 방문하지 않은 노드를

모두 큐에 삽입하고 방문 처리를 한다.

3. 2번의 과정을 더 이상 수행할수 없을때까지 반복!

 

---

출력해야 하는 값은 visited[100]이다.

100이 도착점이니까

 

 

'''
최소 몇 번만에 도착점에 도착할 수 있을까 ? => BFS
'''
from collections import deque

N, M = map(int, input().split())  # N : 사다리, M : 뱀
array = [i for i in range(101)]
visited = [-1 for i in range(101)]
for i in range(N):
    x, y = map(int, input().split())
    array[x] = y
for j in range(M):
    u, v = map(int, input().split())
    array[u] = v


def bfs(node):
    queue=deque() # 큐 생성
    queue.append(node) # 큐에 현재 노드 삽입
    visited[node]=0 # 현재 노드 방문 처리
    while queue:
        idx=queue.popleft()
        for i in range(1,7):
            now=idx+i # now는 현재 idx에 주사위 굴린 수 더한 수
            if now>100:
                continue
            array_num=array[now]
            if visited[array_num]==-1: # 방문하지 않은 곳
                queue.append(array_num)
                visited[array_num]=visited[idx]+1



bfs(1)
print(visited[-1])

 

처음에는 사다리와 뱀의 배열을 각각 따로 만들어주려고 했다.

딕셔너리 형태로

그런데 그럴 필요가 없을 것 같다.

array의 idx를 노드 번호로 초기화하고,

만약 12번에 98로 이동하는 사다리가 존재할 경우

array[12]의 원소값을 98로 변경하는 식으로 하면

굳이 배열이 필요가 없다.

-> Index 사용을 효율적으로 할 것

 

문제를 읽고 예제를 하나하나 풀어서 자세히 로직을 살펴볼 것.

 

dfs와 bfs에서는 방문처리 작업이 꼭 필요하다.

 

---