백준 11725번 트리의 부모 찾기

 

 

 

문제 보러가기 : https://www.acmicpc.net/problem/11725

 

 

11725번: 트리의 부모 찾기

 

 

이번 문제는 깊이 우선 탐색(DFS) 문제였습니다.

 

 

 

《문제 풀이》

 

1. 입력 받은 두 정점은 연결되어 있기 때문에 양방향으로 삽입 

2. 1번 정점부터 dfs 수행

3. dfs 수행할 때마다 해당 정점의 방문 여부를 true 로 설정

4. 연결된 정점을 방문하지 않았다면 해당 노드 삽입 (이것이 부모 노드 번호)  

5. 배열 arr 에 저장된 숫자들 출력

 

 

 

《C++ 코드》

 

#include <iostream>
#include <vector>
#define MAX 100001

using namespace std;

int arr[MAX]; // 부모 노드 번호가 담긴 배열  
vector<int> v[MAX];
bool visited[MAX];

void findParent(int node) {
	visited[node] = true;
	
	for(int i=0; i<v[node].size(); i++) {
		int linkNode = v[node][i]; 
		
		// 방문하지 않았다면 	
		if(!visited[linkNode]) {
			arr[linkNode] = node;
			findParent(linkNode);
		}			
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	cin>>N;
	
	for(int i=1; i<N; i++) {
		int node1;
		int node2;
		cin>>node1>>node2;
		
		// 양방향 연결  
		v[node1].push_back(node2);
		v[node2].push_back(node1);
	}

	findParent(1);
	
	for(int i=2; i<=N; i++)
		cout<<arr[i]<<"\n";
		
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

 

baekjoon - 정답 화면