반응형
https://www.acmicpc.net/problem/11725
11725번: 트리의 부모 찾기
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
www.acmicpc.net

[ 문제풀이 ]
먼저 vector를 이용하여 그래프 입력을 받고, 입력받은 그래프를 바탕으로 DFS를 돌려 문제를 풀 수 있습니다. 한번 방문한 노드는 다시 방문할 필요가 없으므로 visited배열을 통해 방문 체크를 해주시면 됩니다.
[ 소스 코드 ]
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 30 31 32 33 34 35 36 37 38 39 40 | #include<iostream> #include<vector> using namespace std; int N; vector<int> list[100001]; int visited[100001]; int parent[100001]; void dfs(int node) { if (visited[node] == 1) return; visited[node] = 1; for (auto next : list[node]) { if (visited[next] != 1) { parent[next] = node; dfs(next); } } } int main() { scanf("%d", &N); for (int i = 0; i < N - 1; i++) { int a, b; scanf("%d %d", &a, &b); list[a].push_back(b); list[b].push_back(a); } dfs(1); for (int i = 2; i <= N; i++) { printf("%d\n", parent[i]); } } | cs |
반응형
'백준' 카테고리의 다른 글
[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++) (0) | 2022.08.02 |
---|---|
[ 백준 ] 1629번 - 곱셈 (C++) (0) | 2022.08.01 |
[ 백준 ] 11444번 - 피보나치 수 6 (C++) (0) | 2022.07.30 |
[ 백준 ] 2243번 - 사탕상자 (C++) (0) | 2022.07.29 |
[ 백준 ] 5719번 - 거의 최단 경로 (C++) (0) | 2022.07.27 |