백준11725번) 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

◇ 문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

◇ 입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

◇ 출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

---

◆ 풀이

서로 연결되어있는 데이터들이 주어지고, 이를 연결한 뒤 부모 노드를 출력하면 되는 문제다.

예제 입력 1부터 살펴봐야겠다.

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

우선 루트는 1이고, 1에 연결된 건 4와 6이다.

4에 연결된 건 2와 7이다. 그리고 6에는 3이 연결되어있다. 최종적으로 3은 5와 연결되어있다.

이렇게 그림을 그리고 나면 부모 노드를 찾는 것은 쉬워진다.

이것을 코드로 어떻게 구현할 수 있을까?

고민하다가 찾아보니 dfs 알고리즘을 사용하면 된다고 했다.

dfs 알고리즘을 내가 직접 구현해본적은 없어서 일단 따라 쳐보기로 했다.

◆ 받아쓰기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static ArrayList<ArrayList<Integer>> edges = new ArrayList<>();
    private static boolean[] visited;
    private static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int totalCount = Integer.parseInt(br.readLine());
        for(int i=0, iMax = totalCount+1; i<iMax; i++){
            edges.add(new ArrayList<>());
        }

        StringTokenizer st;
        for(int i=0, iMax = totalCount-1; i<iMax; i++){
            st = new StringTokenizer(br.readLine());
            int node1= Integer.parseInt(st.nextToken());
            int node2= Integer.parseInt(st.nextToken());

            edges.get(node1).add(node2);
            edges.get(node2).add(node1);
        }

        visited = new boolean[totalCount+1];
        parent = new int[totalCount+1];

        dfs(1);
        for(int i=2, iMax = parent.length; i<iMax; i++){
            System.out.println(parent[i]);
        }
    }

    private static void dfs(int node){
        visited[node] = true;
        for(int v : edges.get(node)){
            if(!visited[v]){
                dfs(v);
                parent[v] = node;
            }
        }
    }
}

재귀는 실무에서도 잘 사용하지 않아 익숙하지 않아서 여러번 생각을 해야하기 때문에 아직 어렵다.

하지만 재귀를 사용하지 못하면 안 되니... 처음 재귀를 배웠던 떄로 돌아가 코드를 분석해야겠다.

 

◆ 코드 분석

먼저 입력을 받은 연결된 노드를 넣을 List를 생성해 초기화해준다.

여기서 중요한 점은 이 코드를 실행하고 나면 edges ArrayList의 size는 totalCount+1이 된다는 점이다.

for(int i=0, iMax = totalCount+1; i<iMax; i++){
    edges.add(new ArrayList<>());
}

그 이유는, 전체 코드를 살펴보니 edges의 0번 인덱스는 사용하지 않기 때문인 것으로 보인다.

실제로 edges를 배열로 만들고 0번 인덱스에 null을 넣어도 코드는 문제 없이 돌아간다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
// 배열로 바꾸어 보았다.
    private static ArrayList<Integer>[] edges;
    private static boolean[] visited;
    private static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int totalCount = Integer.parseInt(br.readLine());
        edges = new ArrayList[totalCount+1];
        for(int i=0, iMax = totalCount+1; i<iMax; i++){
        // 0번 인덱스는 사용하지 않는다는 것을 증명하기 위해 0번 인덱스에는 null을 넣어보았다.
            if(i!=0)
                edges[i] = new ArrayList<>();
        }

        StringTokenizer st;
        for(int i=0, iMax = totalCount-1; i<iMax; i++){
            st = new StringTokenizer(br.readLine());
            int node1= Integer.parseInt(st.nextToken());
            int node2= Integer.parseInt(st.nextToken());

            edges[node1].add(node2);
            edges[node2].add(node1);
        }

        visited = new boolean[totalCount+1];
        parent = new int[totalCount+1];

        dfs(1);
        for(int i=2, iMax = parent.length; i<iMax; i++){
            System.out.println(parent[i]);
        }
    }

    private static void dfs(int node){
        visited[node] = true;
        // 배열이기 때문에 get함수를 사용하지 않는다
        for(int v : edges[node]){
            if(!visited[v]){
                dfs(v);
                parent[v] = node;
            }
        }
    }
}

출력 결과

그리고 한 줄씩 데이터를 불러온 값을 List에 담는다.

StringTokenizer st;
        for(int i=0, iMax = totalCount-1; i<iMax; i++){
            st = new StringTokenizer(br.readLine());
            int node1= Integer.parseInt(st.nextToken());
            int node2= Integer.parseInt(st.nextToken());

            edges.get(node1).add(node2);
            edges.get(node2).add(node1);
        }

edges index	value
1	6, 4
2	4
3	6, 5
4	1, 2, 7
5	3
6	1, 3
7	4

그리고 dfs함수를 트리의 루트인 1부터 실행시킨다.

 

 private static void dfs(int node){
        visited[node] = true;
        for(int v : edges.get(node)){
            if(!visited[v]){
                dfs(v);
                parent[v] = node;
            }
        }
    }

 

뇌내 디버깅을 해보면 아래 순서와 같이 실행될 것이다.

① node == 1

• visited[1] = true
• dfs(6) 호출
• parent[6] 대기
• dfs(4) 호출 대기

② node == 6

• visited[6] = true
• dfs(3)호출
• parent[3] 대기

③ node == 3

• visited[3] = true
• dfs(5) 호출
• parent[5] 대기

④ node == 5

• visited[5] = true

③ 으로 복귀

•  parent[5] = 3;

② 로 복귀

•  parent[3] = 3;

① 로 복귀

• parent[6] = 1
• dfs(4) 호출

⑤ node == 4

• visited[4] = true
• dfs(2) 호출
• parent[2] = 4 대기
• dfs(7) 호출 대기

⑥ node == 2

• visited[2] = true

⑤로 복귀

• parent[2] = 4
• dfs(7) 호출
• parent[7] = 4 대기

⑦ node == 7

• visited[7] = true

⑤로 복귀

• parent[7] = 4

①로 복귀

• parent[4] = 1

함수 종료 .

재귀함수가 대충 어떤 느낌으로 도는지 살짝 감이 오기 시작했다.