[개념]이진트리 넓이우선탐색(BFS) / c & c++ / 제한시간 없음

아래 그림과 같은 이진트리를 넓이우선탐색해 보세요. 간선 정보 6개를 입력받아 처리해보세 요

넓이 우선 탐색 : 1 2 3 4 5 6 7

 

▣ 입력 예시

1 2 1 3 2 4 2 5 3 6 3 7

 

▣ 입력 예시

1 2 3 4 5 6 7

 

<코드> - c++

#pragma warning(disable:4996)
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

int queue[100], front = -1, rear = -1, visit[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);
		map[b].push_back(a);
	}
	queue[++rear] = 1;
	visit[1] = 1;
	while (front < rear) {
		x = queue[++front];
		printf("%d ", x);
		for (i = 0; i < map[x].size(); i++) {
			if (visit[map[x][i]] == 0) {
				visit[map[x][i]] = 1;
				queue[++rear] = map[x][i];
			}
		}
	}
	return 0;
}

큐(Queue)는 스택과 다르게 FIFO(First In First Out)이란 구조를 가진다. front는 큐의 출구를 말하면 rear은 큐의 입구를 말한다. 가장 쉬운 큐의 예시는 매표소에서 표를 사기위해 줄을 서는 경우를 들수 있다. 

 

문제에서는 인접리스트를 사용해 map을 표현했다.(인접행렬도 문제없음).

 

while(front<rear)은 큐안에 남아있지 않을때까지 계속 반복한다는 것을 의미한다.

 

.

 

인접행렬로도 큐(Queue)를 사용해 이 문제를 풀수 있다.

 

<코드> - c

#pragma warning(disable:4996)
#include<stdio.h>
#define MAX 30
int map[MAX][MAX];
int visit[MAX] = { 0 };
int queue[100];
int front = 0, rear = 0;

void bfs(int v) {
	visit[v] = 1;
	queue[rear++] = v;
	printf("%d ", v);

	while (front < rear) {
		int temp;
		temp = queue[front++];
		for (int i = 1; i <= 7; i++) {
			if (visit[i] == 0 && map[temp][i] == 1) {
				visit[i] = 1;
				queue[rear++] = i;
				printf("%d ", i);
			}
		}
	}
}

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

	bfs(1);

	return 0;
}