1. 개요

 그래프 문제를 풀기 위해서는 그래프 운행을 위한 메커니즘이 필요하다. (일반 운행법으로는 풀 수 없다. 중요!) 이를 

그래프 탐색 알고리즘이라고 한다. 이에 관한 두 가지 기초이자 가장 중요한 알고리즘이 있다.

● DFS (Depth First Search) 깊이 우선 탐색

● BFS (Breath First Search) 넓이 우선 탐색

이다. 두 기법의 가장 큰 차이는 이렇다.

(1) DFS는 비밀이야기다. 한 번에 한 사람에게만 전해진다. BFS는 소문이다. 자기가 아는 모든 사람에게 전한다.

(2) DFS는 모든 노드를 탐색 후 자신에게 돌아와야 끝난다. BFS는 모든 노드를 탐색 후 끝난다.

(3) 두 기법다 매트릭스 그래프일 경우 시간복잡도는 O(V^2)이고, 인접리스트 기반일 경우 O(V+E)다.

(4) 무엇이 더 좋고 나쁜지는 없다. 찾으려는 데이터가 어디에 위치해있는지에 따라 다르다.

(5) DFS는 역추적 과정이 있어 스택 또는 리커젼을 사용. BFS는 현재 연결된 모든 노드를 차례대로 찾기에 를 사용.


2. 문제

 매트릭스 기법으로 최대한 간단하게 BFS 운행법을 코드로 작성하시오. (리커젼 사용)

 그래프의 모양은 다음과 같다.


3. 코드

3-1) 메인


3-2) 그래프 생성


3-3) DFS 알고리즘


3-4) 출력


4. 해설

 딱 2가지만 기억하자.

 (1) 스승님은 위대하다.

 (2) DFS는 시작위치에서 다시 시작위치로 돌아와야 끝나는 알고리즘이다.



+ Recent posts