[BOJ/JAVA] 11725. 트리의 부모 찾기

---

문제 설명

문제 링크

입력 예시

7
1 6
6 3
3 5
4 1
2 4
4 7

출력 예시

4
6
1
3
1
4

---

접근 방법

문제를 슥 훑어봤을 때는 트리 문제인가 했는데 그림을 그려보니 정확하게는 그래프 탐색 문제였다.(그래프가 결국 트리의 특수한 형태이기 때문이다) 간선 정보를 입력받고, BFS를 구현하여 해결하면 된다. BFS 의 기본적인 과정, 순회하는 정점을 queue 에 넣기 전에 꺼냈던 정점이 그 정점의 부모 노드가 되므로 각각 저장해주는 과정만 더해주면 된다.
그러나 BufferedReader 와 BufferedWriter 를 사용했음에도 시간 초과가 여러 번 떴었는데, 그래프의 인접 리스트를 LinkedList 에서 ArrayList 로 바꿨더니 해결되었다. LinkedList 가 시간이 더 걸리는 것 같다.

소스 코드

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

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

        ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
        int n = Integer.parseInt(br.readLine());
        for(int i=0; i<n; i++) adjList.add(new ArrayList<>());

        for (int i=0; i<n-1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adjList.get(a-1).add(b-1);
            adjList.get(b-1).add(a-1);
        }

        boolean[] visited = new boolean[n];
        int[] parent = new int[n];
        LinkedList<Integer> queue = new LinkedList<>();

        // 루트부터 시작하는 BFS
        queue.add(0);
        visited[0] = true;
        while(!queue.isEmpty()) {
            int v = queue.poll();
            for(int a: adjList.get(v)) {
                if(!visited[a]) {
                    parent[a] = v;
                    visited[a] = true;
                    queue.add(a);
                }
            }
        }

        for(int i=1; i<n; i++) bw.write((parent[i]+1)+"\n");
        bw.flush();
    }
}

제출 결과

---

마무리하며

코딩테스트에서 자주 나온다고 하는 알고리즘 유형 중 하나인 그래프 탐색을 구현하는 문제였다. BFS 를 바로 떠올려서 풀긴 했지만 시간 초과가 좀 여러번 나왔는데, 사소해 보이는 부분도 영향을 주는 것을 확인한 만큼 시간관리에 신경써야겠다.