문제 탐색하기

입력값 자료 정리

1. 입력값 N은 노드의 개수를 의미하면서도, 노드의 최대 번호를 의미한다
2. 이후 들어오는 두 입력값은 노드의 번호로 서로 연결된다는 것을 의미한다

해결방법 추론

1. 일단 노드는 양방향으로 연결시켜준다.
   자식으로 부모를 볼 수도 있고, 부모로 자식을 볼 수도 있기 때문이다
2. 트리의 루트가 1이라는 조건이 주어졌다면, 루트 노드부터 시작해서 자식노드를 탐색한다면
   현재 노드의 부모가 누구인지 쉽게 알 수 있을 것이다
3. 따라서 탐색 방법으로 트리의 DFS 탐색을 선택한다면 쉽게 정답을 찾을 수 있을 것이다
4. 또한 탐색할 때, 방문배열을 활용한다면 탐색의 횟수를 줄여 더 효율적으로 DFS 탐색을
   할 수 있을 것이다

시간복잡도 계산

1. DFS라서 시간복잡도를 어떻게 계산해야할까 고민했는데, 의외로 심플하게 계산할 수 있다
2. 트리의 깊이가 깊든 깊지 않든간에 결국 노드의 개수만큼 탐색을 해야한다
3. 따라서 n만큼의 탐색만 하면 되기 때문에 시간복잡도는 O(n)이 된다
4. n의 최대 입력값은 10만이기 때문에 시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. n은 변수로 보관한다
2. 이후 오는 입력값들은 먼저 a와 b 변수로 각각 받아준다
3. 트리의 노드별로 연결된 노드를 관리하기 위해 리스트 배열을 선언하였다
4. a와 b값을 각각 배열의 인덱스로 하고 서로 반대되는 b와 a를 리스트에 넣어준다
5. 입력값만으로는 어디가 부모인지 알 수 없기 때문에 양방향 연결을 해준다

dfs 탐색 설계

1. dfs탐색을 하기전 방문 체크를 위한 방문 배열을 하나 만들어준다
2. dfs 탐색은 루트 노드부터 시작한다. 따라서 1부터 시작하면된다
3. dfs의 파라미터는 현재 값을 나타내는 now 변수하나만 가지며, 탐색 체크를 한다
4. 이어서 리스트 배열에서 now에 연결되어 있는 노드들을 탐색하여,
   미방문했다면 재귀문으로 해당 노드를 탐색해준다
5. 이때 재귀문을 실행하기 전에 그 연결된 노드의 부모를 now로 해주면 된다

출력 설계

1. 부모 노드를 관리하기 위해 똑같은 크기의 배열을 만들어 관리한다
2. dfs 탐색에서 결정된 부모를 각 노드의 인덱스에 값으로 저장한다
3. dfs 탐색 종료 후, 2번 인덱스부터 n까지 출력하면 정답이 된다.

정답 코드

(1회차 시도 성공)

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


public class Main {

    static List<Integer>[] lists;
    static int[] arr;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        lists = new List[n+1];
        for (int i = 0; i < n + 1; i++) {
            lists[i] = new ArrayList<>();
        }
        arr = new int[n+1];
        visited = new boolean[n+1];

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

        dfs(1);

        for (int i = 2; i < n + 1; i++) {
            bw.write(arr[i]+"\n");
        }


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

    private static void dfs(int now) {
        visited[now] = true;
        for (Integer i : lists[now]) {
            if(!visited[i]){
                arr[i] = now;
                dfs(i);
            }
        }

    }
}

문제 링크

11725번 - 트리의 부모 찾기