초급 8회차 그래프 탐색

잊기 쉬운 용어

인접 리스트와 인접 행렬을 헷갈리지 말자
내가 자주 쓰는 그 방식은 인접 리스트임
인접 행렬은 다차원 배열을 사용하는 방식임

DFS

DFS는 본래 스택의 성질을 이용한 탐색법이다.
나는 재귀로 구현해왔지만, 사실 이것도 스택의 원리와 똑같다. 재귀라는 것은 시스템 상에 스택이 쌓이고 빠지면서 실행되기 때문이다.

스택을 사용하여 DFS를 하는 방법은 다음과 같다.

일단 시작 정점의 번호를 스택에 넣는다.

그리고 스택의 top에 있는 정점에 대하여 다음을 반복한다.

스택 top에 있는 정점이 이미 방문한 정점이라면 그냥 빼내서 버리고,
아직 방문하지 않은 정점이라면 빼냄과 동시에 그 정점의 자식들을 스택에 차곡차곡 쌓는다.

이 과정을 반복하다 보면 스택이 완전히 비는 시점이 온다. 그때는 모든 정점의 방문이 끝난 것이다.

BFS

BFS는 DFS와 반대로 큐를 사용한다. 방식은 거의 같은데 그냥 큐를 쓰는 것 뿐이다.

자세한 구현법은 아래의 문제풀이 게시글에 나와있다.

#1260 : DFS와 BFS