백준 11725번 : 트리의 부모 찾기 (Java)

🔗 문제 링크

11725번: 트리의 부모 찾기

---

📖 풀이 과정

- 트리 유형의 문제입니다.
- 풀이에는 DFS(스택, 재귀), BFS 여러가지 풀이가 있지만 저는 DFS(재귀)를 이용해서 풀었습니다.
- 트리에 대해서 처음 시작하는 분들에게 좋은 문제라고 생각합니다.

---

💻 코드

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

public class Main {
	static int n;
	static ArrayList<Integer>[] list;
	static int[] parents;
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		list = new ArrayList[n+1];
		parents = new int[n+1];
		visited = new boolean[n+1];
		
		for(int i = 1; i< n+1; i++){
			list[i] = new ArrayList<>();
		}
		
		for(int i = 1; i< n; i++){
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		}
		
		for(int i = 1; i< n+1; i++){
			if(!visited[i]){
				dfs(i);
			}
		}
		
		for(int i = 2; i< n+1; i++){
			System.out.println(parents[i]);
		}
	}
	
	private static void dfs(int i){
		if(visited[i]){
			return;
		}
		visited[i] = true;
		for(int v : list[i]){
			if(!visited[v]){
				parents[v] = i;
				dfs(v);
			}
		}
	}
}