1. 문제

2. 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 노드 개수 입력

		// 트리 구조 표현을 위한 그래프 구현
		ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
		for (int i = 0; i < n; i++)
			tree.add(new ArrayList<>());

		// 그래프 입력
		for (int i = 0; i < n - 1; i++) {
			int n1 = sc.nextInt() - 1;
			int n2 = sc.nextInt() - 1;
			tree.get(n1).add(n2);
			tree.get(n2).add(n1);
		}

		boolean[] visited = new boolean[n]; // 방문 여부 확인용 배열
		int[] parentNode = new int[n]; // 부모 노드 저장 배열

		// BFS
		Queue<Integer> queue = new LinkedList<>();
		queue.add(0);
		visited[0] = true;
		while (!queue.isEmpty()) {
			int v = queue.poll();
			for (int node : tree.get(v))
				if (!visited[node]) {
					visited[node] = true;
					queue.add(node);
					parentNode[node] = v; // 부모 노드 찾은 후 저장
				}
		}

		// 루트 노드를 제외한 나머지 노드의 부모 노드 출력
		for (int i = 1; i < n; i++)
			System.out.println(parentNode[i] + 1);
	}

}

3. 풀이

// Test Code
    1
  4   6
2  7    3
          5

먼저 queue에 루트 노드 1을 push 해준다.
그리고 while문을 통해 queue가 empty일 때까지 탐색을 시작한다.
q에서 pop할 원소는 자식 노드를 검사할 부모 노드이다.

현재 queue는 다음과 같다.

(1) temp=1
queue에서 pop 했으니 현재 queue는 비어있다.
이제 노드 1에 연결된 노드들 중 자식 노드를 검사한다.
노드 1에 연결된 노드들은 graph[1]={6, 4}이고, 6과 4 모두 아직 방문하지 않았다.
두 노드 모두 방문 표시와 queue에 push를 해주고 부모 노드 1을 저장시킨다.

(2) temp=6
이제 노드 6에 연결된 노드들 중 자식 노드를 검사해본다. graph[6]={1, 3} 이다.
노드 1은 이미 방문했기 때문에 아무것도 하지 않았다. 반면 노드 3은 아직 방문하지 않았다.
노드 3을 방문 표시와 queue에 push한 뒤 노드 3에 대한 부모 노드를 저장한다. 이때 부모 노드는 현재 노드인 6이다.

4. 링크

https://www.acmicpc.net/problem/11725
https://iridescent-zeal.tistory.com/38