[백준_11725번] 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

[문제]

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

 

[입력 조건]

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_11725 {
	static int[] parents;
	static boolean[] visited;
	static ArrayList<ArrayList<Integer>> graph=new ArrayList<ArrayList<Integer>>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		parents=new int[n+1];
		visited=new boolean[n+1];
		
		// 연결리스트에 n개의 노드 추가
		for(int i=0;i<=n;i++)
			graph.add(new ArrayList<Integer>());
		
		// 간선 연결 상태 저장
		for(int i=0;i<n-1;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		
		// 방문처리가 되지 않은 노드는 dfs 함수 실행
		for(int i=1;i<=n;i++) {
			if(visited[i]==false)
				dfs(i);
		}
		
		// 2번 노드부터 부모 노드 출력
		for(int i=2;i<=n;i++)
			System.out.println(parents[i]);
	}
	
	public static void dfs(int v) {
		/*
		 * v 노드가 이미 방문했던 노드라면
		 * 해당 노드는 트리의 가장 밑에 있는 노드이기 때문에 재귀함수를 끝낸다.
		 */
		if(visited[v]) 
			return;
		
		visited[v]=true; // 방문처리
		// v 노드와 연결되어 있는 노드 탐색
		for(int i=0;i<graph.get(v).size();i++) {
			// 방문하지 않은 노드라는 것은 아직 부모노드를 구하지 못한 노드라는 의미
			if(!visited[graph.get(v).get(i)]) {
				// v 노드의 다음 노드는 v 노드를 부모로 갖는다. 
				parents[graph.get(v).get(i)]=v;
				dfs(graph.get(v).get(i)); // v 노드의 다음 노드로 재귀호출 
			}
		}
	}
}

 

[고찰] 

 이번 문제는 DFS를 사용하여 해결하는 문제였다. 이번 문제를 풀 때 중요 포인트는 트리를 탐색하게 되면 부모 노드를 먼저 탐색하게 되기 때문에 v 노드는 다음 노드의 부모 노드가 된다는 것이다. 따라서 연결된 모든 노드를 탐색하면서 배열에 이전에 방문한 노드를 부모 노드로 저장하고, 방문처리 하는 방식으로 해결할 수 있다.