[알고리즘] 너비 우선 탐색 Breadth First Search

# 문제 설명

아래 그림과 같은 이진트리를 너비 우선 탐색해봅니다.

간선의 정보를 입력받아 처리합니다.

인접 리스트를 이용합니다.

queue 자료구조를 직접 구현합니다.

너비 우선 탐색은 시작 노드부터 인접한 노드들을 모두 우선 방문하는 방식의 탐색 방법입니다.

 

시작 노드인 노드1을 방문 한 후

노드1에 인접한 노드2, 노드3을 방문합니다.

노드2에 인접한 노드4, 노드5를 방문합니다.

노드3에 인접한 노드6, 노드7을 방문합니다.

노드4는 인접한 노드가 없으므로 끝입니다.

노드5 ~ 노드7은 노드4와 같습니다.

 

다르게 이야기하면

시작 노드부터 간선 한 번에 인접한 노드들을 순회하고,

간선 두 번에 인접한 노드들을 순회하고,

간석 세 번에 인접한 노드들을 순회하는 방식으로 볼 수 있습니다.

 

 

# 입출력 예

입력	출력
1 2 1 3 2 4 2 5 3 6 3 7	1 2 3 4 5 6 7

 

 

# 문제 풀이

#include <stdio.h>
#include <vector>
using namespace std;
int q[10], front=-1, back=-1 , ch[10];
vector<int> map[10];
int main(){
    int i, a, b, x;
    for(i=1; i<=6; i++){
        scanf("%d %d", &a, &b);
        map[a].push_back(b);
    }
    q[++back]=1;
    ch[1]=1;
	
    // front == back 이라면 queue에 더이상 데이터가 없다는 뜻입니다.
    while(front<back){
		
        // 시작 노드
        x=q[++front];
        printf("%d ", x);
		
        // 인접 노드 순회
        for(i=0; i<map[x].size(); i++){
            if(ch[map[x][i]]==0){
                ch[map[x][i]]=1;
                q[++back]=map[x][i];
            }
        }
    }
    return 0;
}

출력 결과
1 2 3 4 5 6 7

 

 

- queue 자료구조를 활용한 너비 우선 탐색의 흐름