백준 / 트리의 부모찾기 / 11725번

[Java] 백준 / 트리의 부모찾기 / 11725번

문제

트리의 부모찾기 문제 링크

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

입력

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

7
1 6
6 3
3 5
4 1
2 4
4 7

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

4
6
1
3
1
4

접근 방식

입력에서 부모와 자식 관계와 상관없이 연결 된 두 정점을 주기 때문에 양방향 그래프를 만든다

1. 양방향 그래프를 만들어 정점 번호를 인덱스로, 그 내부에는 해당 정점과 연결되어있는 점들을 저장한다
2. dfs를 통해 루트부터 탐색하여 해당 점을 방문처리하고 점과 연결되어있는 다른 점을 탐색한다
3. 다른 점을 탐색할 때 이미 방문한 점이라면 해당 점이 부모일 것이기 때문에 부모 배열에 자신을 부모로 저장한다
4. 방문하지 않은 점이라면 dfs를 이어간다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_S2_11725 {
	
	
	static int parent [];
	static boolean visited[];
	static List<ArrayList<Integer>> list;
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		 list = new ArrayList<ArrayList<Integer>>();
		
		for(int i=0;i<=n;i++) {
			list.add(new ArrayList<Integer>());
		}
		
		for(int i=0;i<n-1;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			
			list.get(v1).add(v2);
			list.get(v2).add(v1);
		}
		
		parent = new int[n+1];
		visited = new boolean[n+1];
		dfs(1);
		
		for(int i=2;i<=n;i++) {
			System.out.println(parent[i]);
		}
	}
	
	public static void dfs(int node) {
		visited[node] = true;
		List<Integer> subList = list.get(node);
		if(subList.size() == 0) {
			return;
		}
		
		for(int i=0;i<subList.size();i++) {
			int nextNode = (int)subList.get(i);
			if(visited[nextNode]) {
				parent[node] = nextNode;
			}
			else {
				dfs(nextNode);
			}
		}
	}
	
	
	
	

	
	
}