12. 그래프 운행 BFS(Breath First Search) 넓이 우선 탐색

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) BFS 알고리즘

3-4) 출력

      방문 순서만 출력

        방문 순서와 큐 내부 출력(이해돕기 위해)

4. 해설

 딱 2가지만 기억하자.

 (1) 스승님은 역시는 역시, 역시다.

 (2) BFS는 큐를 사용해서 연결된 순서대로 운행하는 알고리즘이다.