알고리즘) 트리의 부모 찾기(백준 11725번)

 

문제(백준)

 

 최초 작성 시에는 트리를 인접 행렬의 형태로 정의하였다. 1이 트리의 루트임은 알기 때문에, 1부터 시작해서 1의 행렬의 값들이 무조건 1의 자식 노드가 된다. 이 노드들의 행렬을 확인해 인접한 노드이나 부모가 아닌 값을 자식 노드로 여기는 방식을 재귀함수로 구현하였다. 문제는 이렇게 해결한 코드는 메모리 초과로 통과하지 못했다는 점이다..😭

 

  두 번째로 작성한 코드는 인접 리스트를 사용한 방식이다. 일곱개의 리스트 타입의 배열을 생성해 1부터 시작하여 각 노드의 인접 노드 중 부모가 아닌 노드를 자식 노드로 판단해 해당 자식 노드의 부모를 기억하도록 하는 것이다. 코드 상에서 result는 각 노드(인덱스)의 부모(값)를 가지는 배열이고, checked는 이전에 체크한 노드(부모 노드가 됨) 여부를 가리는 배열이다.

cf. 인접 행렬을 인접 리스트로 변경하면서 총 N + 1 크기의 배열이 생겨야 하는 것은 동일하지만, 내부의 배열 혹은 리스트의 크기는 다르다. 인접 행렬은 항상 내부 배열의 크기가 N + 1인 반면에, 인접 리스트는 인접 노드의 수 가 그 크기가 된다.

 

초기 작성 코드

import java.util.Scanner;

// 트리의 부모 찾기(adjacency matrix 사용)
public class Main {
    static int[] result;
    static int num;
    static int[][] matrix;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        num = sc.nextInt();
        matrix = new int[num + 1][num + 1];

        for (int i = 2; i < num + 1; i++) { // != a
            int a = sc.nextInt(); // 첫 번째 값이 항상 부모는 아님
            int b = sc.nextInt();
            matrix[a][b] = 1;
            matrix[b][a] = 1;
        }

        // retrieve
        result = new int[num + 1];
        int parent = 0;
        int node = 1;
        retrieve(parent, node);

        for (int x = 2; x < result.length; x++) System.out.println(result[x]);
    }

    static void retrieve(int parent, int node) {
        if (node <= num) {
            for (int i = 1; i < num + 1; i++) {
                if (node == i) continue;
                if (matrix[node][i] == 1 && i != parent) {
                    result[i] = node;
                    retrieve(node, i);
                }
            }
        }
    }
}

 

개선 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

// 트리의 부모 찾기(adjacency matrix 사용 -> adjacency list 사용으로 변경)
public class Main {
    static int[] result;
    static int num;
    static ArrayList<Integer>[] list;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        num = sc.nextInt();
        list = new ArrayList[num + 1];

        for (int i = 1; i < num + 1; i++) list[i] = new ArrayList<>();

        for (int i = 2; i < num + 1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            list[a].add(b);
            list[b].add(a);
        }

        // retrieve
        result = new int[num + 1];

        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        boolean[] checked = new boolean[num + 1];
        while (!q.isEmpty()) {
            int n = q.poll();
            for (int i = 0; i < list[n].size(); i++) {
                int child = list[n].get(i);
                if (!checked[child]) { // 이미 체크한 노드인지 확인
                    result[child] = n;
                    q.offer(child);
                }
            }
            checked[n] = true;
        }

        for (int i = 2; i < num + 1; i++) System.out.println(result[i]);
    }
}