백준 - 11725 - 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

 

import java.util.*;

/**
 * 백준 - 11725
 */
public class 트리의부모찾기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.nextLine());
        List<List<Integer>> adjacencyMatrix = new ArrayList<>();
        for (int i = 0; i < N + 1; i++) {
            adjacencyMatrix.add(new ArrayList<>());
        }
        for (int i = 0; i < N - 1; i++) {
            String[] input = sc.nextLine().split(" ");
            int data1 = Integer.parseInt(input[0]);
            int data2 = Integer.parseInt(input[1]);
            adjacencyMatrix.get(data1).add(data2);
            adjacencyMatrix.get(data2).add(data1);
        }
        Integer[] parents = bfs(adjacencyMatrix, N);
        for (int i = 2; i < parents.length; i++) {
            System.out.println(parents[i]);
        }
    }

    private static Integer[] bfs(List<List<Integer>> adjacencyMatrix, int N) {
        Integer[] parents = new Integer[N + 1];
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(1);
        parents[1] = -1;

        while (!queue.isEmpty()) {
            Integer currentVertex = queue.poll();
            List<Integer> adjacencyList = adjacencyMatrix.get(currentVertex);
            for (Integer adjacencyVertex : adjacencyList) {
                if (parents[adjacencyVertex] != null) {
                    continue;
                }
                queue.offer(adjacencyVertex);
                parents[adjacencyVertex] = currentVertex;
            }
        }
        return parents;
    }
}

알고리즘

1. 먼저 인접 행렬을 만들어서 인접한 숫자들이 뭐가 있는지 빠르게 조회할 수있는 구조로 준비해줍니다.
2. bfs를 이용해서 하나하나 순회하면서 부모를 찾아준다. 이때 부모가 있으면 방문했다는 의미이기 때문에 따로 방문 체크를 할 필요가 없습니다.
3. 모든 노드를 순회하고 부모를 출력해줍니다.