티스토리 뷰
[ BOJ ] 11725번 : 트리의 부모 찾기
문제 : https://www.acmicpc.net/problem/11725
[ 문제 ]
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
[ 입력 ]
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
[ 출력 ]
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
[ 문제 접근 및 풀이 ]
DFS를 통해서 now라는 변수로 현재 노드를 나타냈으며
양방향 간선이기에 현재 노드에서 부모 노드로 갈 수도 있으므로 현재 노드의 부모 노드도
포함시켜 사이클이 도는 것을 방지했다.
이후 현재 노드의 자식 노드를 돌면서
자식 노드의 부모를 현재 노드로 지정 후 DFS를 돌렸다.
[ 소스 코드 ]
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> V[100001];
int P[100001];
void Q_11725();
void dfs(int now,int pe);
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Q_11725();
}
void Q_11725(){
cin >> N;
for(int i=1;i<N;i++){
int a,b;
cin >> a >> b;
V[a].push_back(b);
V[b].push_back(a);
}
dfs(1,0);
for(int i=2;i<=N;i++) cout << P[i] <<"\n";
}
void dfs(int now,int pe){
for(auto x:V[now]){
if(x==pe) continue;
P[x]=now;
dfs(x,now);
}
}

'BOJ' 카테고리의 다른 글
[ BOJ / C++ ] 17352번 : 여러분의 다리가 되어 드리겠습니다! (0) | 2025.05.25 |
---|---|
[ BOJ / C++ ] 14499번 : 주사위 굴리기 (0) | 2025.05.25 |
[ BOJ / C++ ] 1991번 : 트리 순회 (0) | 2025.05.18 |
[ BOJ / C++ ] 1240번 : 노드사이의 거리 (0) | 2025.05.18 |
[ BOJ / C++ ] 15681번 : 트리와 쿼리 (0) | 2025.05.11 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 분할 정복을 이용한 거듭제곱
- 백준
- 그래프 탐색
- 시뮬레이션
- BOJ
- 다이나믹 프로그래밍
- C++
- 그래프
- 슬라이딩 윈도우
- 분리 집합
- 트리에서의 다이나믹 프로그래밍
- 그리디 알고리즘
- BFS
- 문자열
- 그래프 이론
- 파싱
- 트리를 사용한 집합과 맵
- 해시를 사용한 집합과 맵
- 너비 우선 탐색
- 스택
- 수학
- 깊이 우선 탐색
- 자료 구조
- 누적 합
- 구현
- 재귀
- 브루트포스 알고리즘
- 트리
- 정렬
- 순열 사이클 분할
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함