아래 그림과 같은 이진트리를 넓이우선탐색해 보세요. 간선 정보 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

``` Cpp

#include <iostream>

#include <vector>

using namespace std;

int Q[100], front = -1, back = -1, ch[10];

vector<int> map[10];

int main() {

FILE* fp = nullptr;

freopen_s(&fp, "input.txt", "rt", stdin);

int i = 0, a = 0, b = 0, x = 0;

for (i = 1; i <= 6; i++) {

cin >> a >> b;

map[a].push_back(b);

map[b].push_back(a);

}

Q[++back] = 1;

ch[1] = 1;

while (front < back) { // Q에 자료가 더 있을 때까지 순환

x = Q[++front];

cout << 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. BFS(넓이 우선 탐색 또는 레벨 탐색)

- Root node 이후 탐색을 할 때 root node의 자식들을 모두 탐색을 하는 것이 넓이 우선 탐색이다.

2. Queue를 저렇게 사용하는 이유는 실제로 출력을 하기 위한 pos 값(front)과 데이터를 저장하기 위한 pos 값(back)을 각각 구분하기 위함이다.

다음 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요.


첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연

결정보가 주어진다.

1번 정점에서 각 정점으로 가는 최소 간선수를 2번 정점부터 차례대로 출력하세요.

6 9\

1 3\

1 4\

2 1\

2 5\

3 4\

4 5\

4 6\

6 2\

6 5

2 : 3\

3 : 1\

4 : 1\

5 : 2\

6 : 2

``` Cpp

#include <iostream>

#include <queue>

using namespace std;

int ch[21], res[21];

vector<int> map[21];

int main() {

FILE* fp = nullptr;

freopen_s(&fp, "input.txt", "rt", stdin);

int i = 0, n = 0, m = 0, a = 0, b = 0, x = 0;

queue<int> q;

cin >> n >> m;

for (i = 1; i <= m; i++) {

cin >> a >> b;

map[a].push_back(b);

}

q.push(1);

ch[1] = 1;

while (q.size() > 0) {

x = q.front();

q.pop();

for (i = 0; i < map[x].size(); i++) {

if (ch[map[x][i]] == 0) {

ch[map[x][i]] = 1;

q.push(map[x][i]);

res[map[x][i]] = res[x] + 1;

}

}

}

for (i = 2; i <= n; i++) {

cout << i << " : " << res[i] << endl;

}

return 0;

}

1. 풀이 전략만 듣고 단 한번에 구현 성공한 문제.

2. 이 맛에 알고리즘 공부를 하는가보다.