깊이 우선 탐색

탐색이란?

탐색이란 가능성을 조사하면서 해를 찾는 방법.

깊이 우선 탐색이란?

가장 기초적인 탐색 방법.

이 기사에서 배우는 것

깊이 우선 탐색을 통한 "채우기"

깊이 우선 검색의 재기 함수에 의한 구현

깊이 우선 탐색의 스택 구현

문제

입력

그림과 같은 미로

출력

s에서 g까지 갈 수 있습니까

채우기 플러드필

문제 해결 방법

s에서 갈 수있는 모든 곳을 찾습니다

g로 가면 'yes', 갈 수 없으면 'no'

채우는 것은 "s에서 갈 수 있는 장소를 전부 알아내는"방법이고, 아주 잘 사용된다.

깊이 우선 탐색에 의한 채우기

기본 사고 방식

지금 있는 곳에서 옆에 가려고 한다

아직 가지 않았다면

제대로 채우기 위해
* 모든 곳에서 4 방향으로의 이동을 위해 다
* 그렇게 하기 위해 다하지 않는 곳을 기억하고 돌아온다.
* 돌아와서 다른 곳으로 갈 수 있으면 그쪽으로 가
* 시작 지점으로 돌아오면 완료

왜 깊이 우선 탐색이라고 하는가

아직 4방향을 시도하지 않은 곳 중에서 가장 깊은 바요에서 탐색을 펼치기 때문에

재귀 함수에 의한 깊이 우선 탐색

사고방식

위치를 인수로 한 재귀 함수 사용

자신으로부터 4방향으로의 호출을 한다

왜 이것으로 깊이 우선 탐색이 되는가

재귀 함수이므로 호출한 후 돌아온다

돌아와 다른 방향으로 다시 호출

의사 코드

関数 search(x, y) {
   if (場所 (x, y) が壁か迷路の外) return 
   if (既に (x, y) に一度到達している) return
   (x, y) に到達したということを記録

　　//4方向を試す
   //再帰関数なので1つの方向を試しおわた後帰ってきて次の方向を試す
   search(x + 1, y)
   search(x - 1, y)
   search(x, y + 1)
   search(x, y - 1)
}

스택에 의한 깊이 우선 탐색

사고방식

시도할 위치를 스택으로 관리

재귀 호출 대신 스택에 push

알고리즘

처음에는 시작점을 스택에 투입

반복 : 스택에서 위치를 꺼내고 아직 방문하지 않은 옆이 있으면 push

재귀 함수가 너무 깊어지면 "스택 오버플로"가 발생하여 런타임 오류가 발생할 수 있습니다.
스택을 사용하는 방법이라면 이것을 피할 수 있습니다.

깊이 우선 탐색 요약

깊이 우선 탐색의 다른 차례

모든 조합을 사용해보십시오.

그 고속화인 가지 깎기 탐색

깊이 이외를 우선하는 탐색

폭 우선 탐색

재량 우선 탐색 (→ Dijkstra/Prim 알고리즘)

참고
A - 깊이 우선 탐색