69. 이진트리 넓이 우선 탐색 [BFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

1 2

1 3

2 4

2 5

3 6

3 7

 

출력예제 1

1 2 3 4 5 6 7

 

풀이 

- 큐를 배열로 구현(선입선출 구조, 먼저 들어온것이 먼저 나감 <-> 스택: 후입선출)

- front와 back을 이용한다 (둘 다 -1로 초기화)

* front: back을 따라가며 하나씩 출력함

* back: 해당 정점에 연결된 정점을 배열에 넣어줌

 

Q[0]=1;

ch[1]=1; 을 해준 후 시작 (back = 0, front = -1인 상태)

while(front<back) => front가 back을 따라가면서 출력하기 때문에 front는 back보다 작아야한다

x=Q[++front] => x변수를 사용해 들어온 1을 출력한다. front=0으로 증가시킨다.

for(i=0;i<map[x].size();i++) => x에 연결된 정점을 탐색하기 하기 위해 for문 사용

if(ch[map[x][i]]==0) => 방문하지 않았으면

ch[map[x][i]]=1 => 체크를 1로 변경 후

Q[++back]=map[x][i]; => back을 움직여 연결된 정점인 map[x][i] 값을 넣어준다 (back=1, front=0)

 

#include<stdio.h>
#include<vector>
using namespace std;
int Q[100], front=-1, back=-1, ch[10];
vector<int> map[10];

//69. 이진트리 넓이우선탐색(BFS) = 레벨탐색 > 큐 사용
int main(){
    int i, a, b, x;
    for(i=1;i<=6;i++){
        scanf("%d %d", &a, &b);
        map[a].push_back(b);
        map[b].push_back(a);
    }
    Q[++back]=1;
    ch[1]=1;
    while (front<back) {
        //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;
}