똑똑한 코드 작성을 위한 실전 알고리즘

239

7

장

그래프

➊

node_from

구조는

src

에서 모든

target

으로 가는 경로를 복구하는 데 필요하다.

➋

경로를 복구하기 위해

v

를

target

으로 설정한다.

➌

v

가

src

가 아니라면

v

를

path

에 추가하고,

path

는

src

에서

target

까지 경로의 역방향 리스트가 된다.

➍

node_from[v]

에 기록된 이전 노드를

v

로 설정해 역방향 이동을 계속한다.

➎

src

에 도달하면

while

루프가 종료되며, 역방향

path

를 완성하기 위해

src

가 반드시 추가되어야 한다.

➏

src

에서

target

까지 알맞은 순서를 생성하기 위해

path

의 역순을 반환한다.

➐

node_from[]

이

target

을 포함하지 않는다면

src

에서 도달 가능하지 않다는 의미다.

path

_

to

()

함수는

target

에서 역방향으로

src

를 만날 때까지 역순으로 일련의 노드를 계산

한다. 그리고 나서 단순히 노드 순서를 뒤집어 알맞은 순서로 해결책을 생성한다. 도달할 수 없

는 노드로의 경로를 복구하려 하면

path

_

to

()

는

ValueError

를 일으킬 것이다.

깊이 우선 탐색은 목적지에서 단 하나의 노드만 떨어져 있다고 예상하고 임의의 방향으로 반복

해서 탐색하는 것이다. 이제 좀 더 체계적인 탐색 전략을 살펴보자.

7.3

너비 우선 탐색으로 미로 풀기

너비 우선 탐색 ...