69. 이진트리 넓이우선 탐색(BFS):큐 자료구조 직접 구현

it 취업을 위한 알고리즘 문제 풀이

문제

코드

//69. 이진트리 넓이우선 탐색(BFS)

#include<stdio.h>
#include<vector>
using namespace std;


int main() {
    freopen("input.txt", "rt", stdin);
    int Q[10] = {0}, visited[10] = { false, };
    int front=-1, rear=-1, x, a, b,firstX = 1;
    vector<int> map[10];

    for (int i = 0; i < 6; ++i) {
        scanf("%d %d", &a, &b);
        map[a].push_back(b);
        map[b].push_back(a);
    }

    Q[++rear] = firstX;
    visited[firstX] = true;

    while (front < rear) {
        x = Q[++front];
        printf("%d ", x);
        for (int i = 0; i < map[x].size(); ++i) {
            if (visited[map[x][i]] == false) {
                Q[++rear] = map[x][i];
                visited[map[x][i]] = true;
            }
        }
    }

    return 0;
}

문제해결방법

• 입력된 트리 정보를 연결리스트 방식으로 저장한다.
• 저장된 트리를 큐자료구조를 이용해 BFS 탐색한다.