포인트
- 트리 정의하기 -> 인접리스트 사용: 벡터를 사용하기
- 트리 순회하기 -> bfs: 큐를 사용하여 모든 노드를 순회한다.
- 주의: 매번 검색하면 시간 초과가 난다. 한번 순회하면서 부모노드를 모두 저장한다.
#include <stdio.h>
#include <vector>
#include <queue>
#define MAX 100000 + 1
using namespace std;
vector<int> v[MAX];
int result[MAX];
int root = 1;
void findParent()
{
queue<int> q;
int flag[MAX] = {
0,
};
q.push(root);
flag[root] = 1;
while (!q.empty())
{
int cur = q.front();
q.pop();
for (int i = 0; i < v[cur].size(); i++)
{
int nxt = v[cur][i];
if (flag[nxt])
continue;
result[nxt] = cur;
q.push(nxt);
flag[nxt] = 1;
}
}
}
int main(void)
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int x, y;
scanf("%d %d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
findParent();
for (int i = 2; i <= n; i++)
{
printf("%d\n", result[i]);
}
return 0;
}
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 13913] 숨바꼭질 4 (0) | 2020.11.01 |
---|---|
[백준 13549] 숨바꼭질3 (0) | 2020.10.29 |
[백준 1600] 말이 되고픈 원숭이 (0) | 2020.10.29 |
[백준 6593] 상범빌딩 (0) | 2020.10.28 |
[백준 7569] 토마토 (0) | 2020.10.27 |
댓글