[백준] 11725번 : 트리의 부모 찾기 - JAVA [자바]

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

트리 문제이지만 그래프로 풀 수 있다.

트리는 그래프의 특수한 형태로 어떤 정점의 인접한 정점은 반드시 부모 노드 혹은 자식 노드라는 특징이 있다. 이를 이용하여 루트 노드에서부터 방문 여부를 저장하며 탐색을 하면 어떠한 노드에서 인접한 노드들 중 아직 방문하지 않은 노드는 나의 자식 노드라는 것을 알 수 있고 그 자식 노드의 부모는 내 노드라는 것을 알 수 있다.

public static void bfs(int start) {
	Queue<Integer> queue = new LinkedList<>();
    queue.add(start);

	while (!queue.isEmpty()) {
    	start = queue.poll();
        visited[start] = true;

		for (int to : edgeList.get(start)) {
        	if (!visited[to]) {
            	parent[to] = start;
                queue.add(to);
			}
		}
	}
}

bfs 알고리즘을 통해 인접한 노드들을 탐색하며 방문 여부에 따라 자식 노드를 판별하여 부모 노드를 저장한다.

public class bj11725 {

    public static int N;
    public static int[] parent;
    public static boolean[] visited;
    public static StringBuilder sb = new StringBuilder();
    public static ArrayList<ArrayList<Integer>> edgeList;

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        parent = new int[N + 1];
        visited = new boolean[N + 1];
        edgeList = new ArrayList<>();

        for (int i = 0; i <= N; i++) {
            edgeList.add(new ArrayList<>());
        }

        for (int n = 0; n < N - 1; n++) {
            String line = br.readLine();
            String[] split = line.split(" ");
            int num1 = Integer.parseInt(split[0]);
            int num2 = Integer.parseInt(split[1]);
            edgeList.get(num1).add(num2);
            edgeList.get(num2).add(num1);
        }

        bfs(1);

        for (int i = 2; i <= N; i++) {
            sb.append(parent[i]).append("\n");
        }

        bw.write(sb + "");

        bw.flush();
        bw.close();
        br.close();
    }

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            start = queue.poll();
            visited[start] = true;

            for (int to : edgeList.get(start)) {
                if (!visited[to]) {
                    parent[to] = start;
                    queue.add(to);
                }
            }
        }
    }
}