BOJ : https://www.acmicpc.net/problem/11725
GitHub : https://github.com/junho0956/Algorithm/blob/master/11725/11725/%EC%86%8C%EC%8A%A4.cpp
처음에는 입력이 번호 순서대로 주어지는 것인줄 알고 풀었다가 틀리고
그 다음에는 마구잡이가 된다는걸 알고 그냥 마구잡이로 아직 루트가 없는 노드는 큐에 넣어서
다시 확인하는 방법으로 풀었다가 시간초과가 나고.. 어려운 문제도 아닌데
앞으로는 좀 깔끔하게 정확하게 풀어가는 습관을 기를 수 있게 노력해야겠다;
마구잡이식으로 확인하면 무조건 시간초과가 뜨니
입력을 전부 받아놓고 루트부터 트리를 만들어가는 느낌으로 확인만 해주자
더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include <iostream>
#include <vector>
using namespace std;
int arr[100001], v1, v2, N;
vector<int> v[100001];
void dfs(int num) {
for (int i = 0; i < v[num].size(); i++) {
if(!arr[v[num][i]]) arr[v[num][i]] = num, dfs(v[num][i]);
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> N;
for (int i = 0; i < N - 1; i++) {
cin >> v1 >> v2;
v[v1].push_back(v2);
v[v2].push_back(v1);
}
dfs(1);
for (int i = 2; i <= N; i++)
cout << arr[i] << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > BOJ' 카테고리의 다른 글
BOJ 1167번 트리의 지름 (0) | 2020.01.15 |
---|---|
BOJ 1967번 트리의 지름 (0) | 2020.01.15 |
BOJ 1991번 트리 순회 (0) | 2020.01.14 |
BOJ 2146번 다리 만들기 (0) | 2020.01.14 |
BOJ 2178번 미로탐색 (0) | 2020.01.14 |