백준 11725

문제

---

루트 노드부터 시작하여 BFS로 자식노드를 탐색함

부모 노드를 큐에 저장하고 연결된 (자식)노드를 모두 확인

연결된 노드 중 방문한 적이 없는 노드를 다음 탐색할 노드로 지정하고

해당 노드의 부모 노드를 저장했다가 마지막에 출력

---

Code

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P11725 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		
		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++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			tree.get(a).add(b);
			tree.get(b).add(a);
		}
		
		boolean[] visited = new boolean[N];
		int[] parentNode = new int[N];
		
		Queue<Integer> q = new LinkedList<>();
		q.add(0);
		visited[0] = true;
		while(!q.isEmpty()) {
			int v = q.remove();
			for(int node : tree.get(v)) {
				if(!visited[node]) {
					visited[node] = true;
					q.add(node);
					parentNode[node] = v;
				}
			}
		}
		
		for(int i = 1; i < N; i++) {
			sb.append(parentNode[i] + 1).append('\n');
		}
		bw.write(sb.toString());
		
		br.close();
		bw.flush();
		bw.close();
	}

}

---

참고 : https://velog.io/@darak/BJ-11725-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EB%B6%80%EB%AA%A8-%EC%B0%BE%EA%B8%B0-Java