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

풀이 ① - Tree + DFS

1. 아이디어

• Tree를 직접 구현 X

  • 트리의 자식 노드 개수에 제한이 없음
    (이진 트리처럼 Left Child, Right Child 형식 X)
  • 노드의 연결 정보가 부모 - 자식 순서로 정해져서 입력되지 않음

  => Tree를 직접 구현 X, 그래프 탐색으로 해결

• 트리 노드 연결 정보 저장
  => n x n 의 인접 행렬 int[][] 사용 시, 메모리 초과
  => 인접 리스트 List<Integer>[] 사용

• 1번 루트 노드에서부터 연결된 자식 노드들을 차례로 DFS 탐색하여,
  배열 형태로 각 노드들의 부모 노드를 저장해나감
  1) 부모 노드 방문 처리
  2) 부모 노드에 연결된 노드들 중, 아직 방문 안한 노드들에 대해 탐색 확장 (재귀 호출)

  • 부모 노드와 연결된 노드들 중, 아직 방문 안한 노드가 자식 노드가 됨

  • 트리 탐색: 부모 노드가 자식 노드보다 항상 먼저 방문됨

2. 자료구조

• List<Integer>[], ArrayList<Integer>[]: 인접 리스트
• boolean[]: 부모 노드 방문 확인

3. 시간 복잡도

• 루트 노드에서 시작하여 DFS 1번 수행
  => O(V + E)
  => V: n (최대 10^5)

코드

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

public class Main_DFS {
	static int n;			// 노드의 개수
	static List<Integer>[] lists;	// 인접 리스트
	static boolean[] checkParent;	// 부모 노드 방문 확인
	static int[] parents;		// 출력 값: 각 노드들의 부모 노드 index

	static void dfs(int idx) {
		checkParent[idx] = true;

		List<Integer> list = lists[idx];	// idx 번 노드와 연결된 노드들
		for (int nextIdx : list) {
			// nextIdx 를 아직 방문 안한 경우 => nextIdx 가 자식 노드
			// => 부모 노드 idx 는 자식 노드 nextIdx 보다 먼저 방문됨
			if (!checkParent[nextIdx]) {
				parents[nextIdx] = idx;
				dfs(nextIdx);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		checkParent = new boolean[n + 1];
		parents = new int[n + 1];
		lists = new ArrayList[n + 1];		// [1 ~ n] 사용
		for (int i = 1; i <= n; i++)
			lists[i] = new ArrayList<>();

		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int idx1 = Integer.parseInt(st.nextToken());
			int idx2 = Integer.parseInt(st.nextToken());

			lists[idx1].add(idx2);
			lists[idx2].add(idx1);
		}

		dfs(1);		// 루트 노드에서 탐색 시작

		// 2 ~ n 번 노드의 부모 노드 차례로 출력
		StringBuilder sb = new StringBuilder();
		for (int i = 2; i <= n; i++)
			sb.append(parents[i]).append("\n");
		System.out.println(sb);
	}
}

풀이 ② - Tree + BFS

1. 아이디어

• Tree를 직접 구현 X

  • 트리의 자식 노드 개수에 제한이 없음
    (이진 트리처럼 Left Child, Right Child 형식 X)
  • 노드의 연결 정보가 부모 - 자식 순서로 정해져서 입력되지 않음

  => Tree를 직접 구현 X, 그래프 탐색으로 해결

• 트리 노드 연결 정보 저장
  => n x n 의 인접 행렬 int[][] 사용 시, 메모리 초과
  => 인접 리스트 List<Integer>[] 사용

• 1번 루트 노드에서부터 연결된 자식 노드들을 차례로 BFS 탐색하여,
  배열 형태로 각 노드들의 부모 노드를 저장해나감
  1) 부모 노드 방문 처리
  2) 부모 노드에 연결된 노드들 중, 아직 방문 안한 노드들에 대해 탐색 확장 (Queue에 추가)

  • 부모 노드와 연결된 노드들 중, 아직 방문 안한 노드가 자식 노드가 됨

  • 트리 탐색: 부모 노드가 자식 노드보다 항상 먼저 방문됨

2. 자료구조

• Queue<Integer>, LinkedList<Integer>: BFS
• List<Integer>[], ArrayList<Integer>[]: 인접 리스트
• boolean[]: 부모 노드 방문 확인

3. 시간 복잡도

• 루트 노드에서 시작하여 BFS 1번 수행
  => O(V + E)
  => V: n (최대 10^5)

코드

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

public class Main_BFS {
	static int n;			// 노드의 개수
	static List<Integer>[] lists;	// 인접 리스트
	static boolean[] checkParent;	// 부모 노드 방문 확인
	static Queue<Integer> queue = new LinkedList<>();
	static int[] parents;		// 출력 값: 각 노드들의 부모 노드 index

	static void bfs() {
		while (!queue.isEmpty()) {
			int idx = queue.remove();

			List<Integer> list = lists[idx];	// idx 번 노드와 연결된 노드들
			for (int nextIdx : list) {
				// nextIdx 를 아직 방문 안한 경우 => nextIdx 가 자식 노드
				// => 부모 노드 idx 는 자식 노드 nextIdx 보다 먼저 방문됨
				if (!checkParent[nextIdx]) {
					checkParent[nextIdx] = true;
					parents[nextIdx] = idx;
					queue.add(nextIdx);
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		checkParent = new boolean[n + 1];
		parents = new int[n + 1];
		lists = new ArrayList[n + 1];		// [1 ~ n] 사용
		for (int i = 1; i <= n; i++)
			lists[i] = new ArrayList<>();

		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int idx1 = Integer.parseInt(st.nextToken());
			int idx2 = Integer.parseInt(st.nextToken());

			lists[idx1].add(idx2);
			lists[idx2].add(idx1);
		}

		// 루트 노드에서부터 탐색 시작
		checkParent[1] = true;
		queue.add(1);
		bfs();

		// 2 ~ n 번 노드의 부모 노드 차례로 출력
		StringBuilder sb = new StringBuilder();
		for (int i = 2; i <= n; i++)
			sb.append(parents[i]).append("\n");
		System.out.println(sb);
	}
}