티스토리 뷰

링크 : www.acmicpc.net/problem/11725

문제요약

입력 : N, 각각 연결된 노드들

 

출력 :  N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력

코드작성개요

필요한 변수 

N - 받을 노드의 줄

a, b - 연결된 노드

now - 지금 탐색중인 노드

 

필요한 배열(vector)

adj - vector 형 배열로 인접리스트(트리)구현

visited - 방문체크

parents - i 번째 노드의 부모

 

깊이 우선 탐색(DFS) 

1. 루트가 1이므로 처음 now 값 1로 전달

2. 1부터 자신의 자식 노드를 탐색

3. 다음에 탐색할 노드의 부모를 now로 설정하고 parents[다음 탐색할 노드] 에 now 값을 넣는다

 

코드

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj;
vector<bool> visited;
vector<int>parents;
void dfs(int now)
{
visited[now] = true;
for(int i : adj[now]){
if(!visited[i]){
parents[i] = now;
dfs(i);
}
}
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
adj.resize(N + 1);
parents.resize(N + 1);
visited.resize(N + 1);
for(int i = 0; i < N-1; i++){
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1);
for (int i = 2; i <= N; i++)
cout << parents[i] << "\n";
}

 

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2025/04   »
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
글 보관함