7장 트리 - (3) 트리의 탐색

1. 트리의 탐색 

- 이진 트리가 아닌 경우 인오더 방식의 순회는 어떤 자식을 루트로 잡아 줄지가 명확하지 않아 불가능

- 트리의 탐색은 DFS/BFS 알고리즘을 이용해서 할 수 있음(어차피 그래프이기 때문)

- 트리는 사이클이 없는 그래프이기 때문에

- 임의의 두 정점 사이의 경로는 항상 1개이다.

- 따라서, BFS 알고리즘을 이용해서 최단 거리를 구할 수 있다.

- 이유 : 경로가 1개라 찾은 그 경로가 최단 경로

2. 문제

- 트리의 부모 찾기(11725번)

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

vector<int> a[100001];

int parent[100001];

bool check[100001];

void bfs(int x) {

queue<int> q;

q.push(x);

check[x] = true;

while (!q.empty()) {

x = q.front();

q.pop();

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

int y = a[x][i];

if (check[y]==false) {

check[y] = true;

parent[y] = x;

q.push(y);

}

}

}

}

int main(void) {

int n;

cin >> n;

for (int i = 0; i < n-1; i++) {

int u, v;

cin >> u >> v;

a[u].push_back(v);

a[v].push_back(u);

}

bfs(1);

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

cout << parent[i] << '\n';

}

return 0;

}

- 트리의 지름(1167번, 1967번)