문제 이해

트리의 루트를 1이라고 지정했을 때, 각 Node의 부모를 구하는 문제이다

---

문제 풀이

BFS, DFS 2가지 방법 모두로 해결할 수 있다.
나는 DFS를 통해 이 문제를 해결했다.

특정 점 A가 재귀함수 fun1, fun2, ..., fun3을 호출했다고 가정하자.
이 경우, func1, fun2,..., func3에서 처리하는 점은 2개 Case 중 하나이다.
A의 부모이거나, A의 자식이거나.

A의 부모의 경우 이미 visit한 점이므로 이미 visit했다는 것이 드러나면 바로 재귀함수를 return(종료) 시키면 될 것이다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static ArrayList<Integer>[] lists;
	static int[] parent;
	static StringBuilder sb = new StringBuilder();
	
	public static void find_parent(int from, int to) {
        // from : 부모 후보, to : 자식 후보
		
		if(parent[to]!=0) return; 
        // parent[to]에 0이 아닌 값이 저장되어 있다는 것은 
        // to점에 대한 부모가 정해져 있다는 의미이다.
        // 즉, 이미 처리가 완료된 점이라는 의미이므로 무시한다.
		
		parent[to] = from;
        // to의 부모 노드를 from으로 지정
		for(int s:lists[to]) {
            // to에 연결된 모든 점에 대해 dfs 다시 수행
			find_parent(to, s);
		}
		
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		
		lists = new ArrayList[N+1];
		parent = new int[N+1];
		
		for(int i = 1;i<N+1;i++) {
			lists[i] = new ArrayList<>();
		}
		
		for(int i =0;i<N-1;i++) {
			int tmp1 = sc.nextInt();
			int tmp2 = sc.nextInt();
			
			lists[tmp1].add(tmp2);
			lists[tmp2].add(tmp1);
		}
		
		for(int s:lists[1]) {
			find_parent(1, s);
		}
		
		for(int  i=2;i<N+1;i++) {
			sb.append(parent[i]).append("\n");
		}
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과