[Grind75-LeetCode] Minimum Height Trees JAVA

반응형

728x90

[Grind75-LeetCode] Minimum Height Trees - Medium

---

접근

• 리프 노드 제거

---

풀이

트리는 두 정점이 하나의 경로로 연결된 무방향 그래프로 사이클이 존재하지 않는 무방향 그래프는 트리라고 부를 수 있다. 트리는 루트에 따라 트리를 구성하는 높이가 달라지는데 이번 문제는 무방향 그래프에서 트리의 높이를 가장 낮게 구성할 수 있는 루트 노드들을 찾아 반환하는 문제이다. 무방향 그래프를 트리로 봤을 때 높이가 3이 최소가 된다면 3의 높이로 트리를 구성할 수 있는 루트 노드를 모두 찾는 것이다. 문제가 점점 어려워지고 있는 것 같다.

 

구할 수 있는 방법은 여러 가지가 있을 것이다. 각 정점 간의 거리를 구해 가장 멀리 있는 두 정점을 구하고 두 정점 가운데 정점을 루트로 사용하면 최소 높이를 구할 수 있지만 엄청난 연산이 필요했다. 저런 방법으로 문제를 풀었는데 코드가 너무 복잡해져 다른 코드들에 비해 길이가 2~3배나 되다 보니 다른 코드를 가져와 리뷰를 해보려고 한다. 리프 노드를 제거하는 방식으로 풀어진 코드를 가져왔다. 리프 노드는 차수가 1인 노드로 트리의 외곽에 존재하는 노드라고 보면 된다. 트리의 지름을 기준으로 생각하면 지름의 양끝 리프 노드들을 제거하며 진행하다 보면 중심에 도달하게 되고 해당 중심은 트리가 가장 낮은 레벨을 유지할 수 있는 루트가 되는 것이다. 트리의 형태에선 루트와 먼 높은 레벨의 연결된 노드들을 제거하며 낮은 레벨로 가게 되고 루트에 도달하는 구조이다. 

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);

        // create the graph
        List<Set<Integer>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; ++i) adj.add(new HashSet<>());
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

n이 1이라면 하나의 노드만 존재하는 것으로 해당 노드가 루트가 되기 때문에 바로 처리를 해준다. 그리고 정점을 연결해 무방향 그래프를 만들어 준다.

	// find leaves
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; ++i)
            if (adj.get(i).size() == 1) leaves.add(i);

정점을 순회하며 연결된 노드가 1개인 리프 노드들을 찾아준다. 

	// trim leaves, not sure why this n>2 is needed, 
        while (n > 2) {
            n -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            for (int i : leaves) {
                int j = adj.get(i).iterator().next();
                adj.get(j).remove(i);
                if (adj.get(j).size() == 1) {
                    newLeaves.add(j);
                }
            }
            leaves = newLeaves;
        }
        return leaves;
    }

위에서 찾았던 리프 노드들을 그래프에서 지우는 과정이다. 노드의 개수가 2개 이하가 될 때까지 계속해준다. 2개 이하가 되어야 하는 이유는 만약 노드가 1개가 있다면 해당 노드가 루트가 된다. 그리고 노드가 2개가 있다면 서로 연결된 상태로돌 중 아무 노드나 선택해도 높이는 2로 동일하기 때문에 상관이 없다. 그러나 노드가 3개가 된다면 그때부터는 어떤 노드를 루트로 선택하냐에 따라 높이가 달라지기 때문이다. 예를 들어 노드가 3개가 일렬로 연결되어 있다면 해당 트리의 높이는 3이 되지만 한 노드에 나머지 두 노드가 연결되어 있다면 노드의 높이는 2가 되기 때문이다. 그렇기 때문에 어떤 노드를 선택해도 높이가 같아지는 2개 이하가 될 때까지 진행해 주는 것이다. 그래프에서 리프 노드와 연결된 노드의 인접 리스트에서 리프 노드를 제거하고 제거한 노드가 리프 노드가 된다면 새로운 리프 노드로 추가해 준다. 

리프 노드 제거

---

배열 + Queue 사용

앞에 성능이 좋은 코드들은 다 사용하는 자료구조에서 오는 차이이다. 핵심 로직 자체는 다 동일하기 때문에 어떤 자료구조를 사용했는지를 중점으로 보면 될 거 같다. 

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1)
            return Collections.singletonList(0);
        List<Integer> tree[] = new ArrayList[n];
        int ind[] = new int[n];

        for (int i = 0; i < n; i++)
            tree[i] = new ArrayList<>();

        for (int i[] : edges) {
            int u = i[0];
            int v = i[1];
            ind[u]++;
            ind[v]++;
            tree[u].add(v);
            tree[v].add(u);
        }

그래프가 Integer 리스트를 가지는 배열을 통해 구성되었다. 아무래도 List와 Set이 중첩된 형태보다 배열의 형태가 더 빠른 성능을 보장하기 때문인 거 같다. 

	Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (ind[i] == 1) {
                q.add(i);
            }
        }

리프 노드를 담는 List에는 Queue가 사용되었다. 큐에서의 연산은 맨 앞과 뒤에서만 일어나기 때문에 O(1)을 만족한다.

	while (n > 2) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int p = q.poll();
                n--;
                for (int j : tree[p]) {
                    ind[j]--;
                    if (ind[j] == 1) {
                        q.add(j);
                    }
                }
            }
        }
        List<Integer> ans = new ArrayList<>();
        ans.addAll(q);
        return ans;
    }

리프 노드를 제거하는 과정으로 제거하고 난 뒤 연결되었던 노드가 리프 노드가 된다면 큐에 다시 추가하는 방식으로 진행된다. 핵심 로직 자체는 동일하지만 사용되는 자료구조의 차이로 성능이 결정되었다.

배열 + Queue

---

전체 코드

List + Set

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);

        // create the graph
        List<Set<Integer>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; ++i) adj.add(new HashSet<>());
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        // find leaves
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; ++i)
            if (adj.get(i).size() == 1) leaves.add(i);

        // trim leaves, not sure why this n>2 is needed, 
        while (n > 2) {
            n -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            for (int i : leaves) {
                int j = adj.get(i).iterator().next();
                adj.get(j).remove(i);
                if (adj.get(j).size() == 1) {
                    newLeaves.add(j);
                }
            }
            leaves = newLeaves;
        }
        return leaves;
    }
}

 

배열 + Queue

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1)
            return Collections.singletonList(0);
        List<Integer> tree[] = new ArrayList[n];
        int ind[] = new int[n];

        for (int i = 0; i < n; i++)
            tree[i] = new ArrayList<>();

        for (int i[] : edges) {
            int u = i[0];
            int v = i[1];
            ind[u]++;
            ind[v]++;
            tree[u].add(v);
            tree[v].add(u);
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (ind[i] == 1) {
                q.add(i);
            }
        }
        
        while (n > 2) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int p = q.poll();
                n--;
                for (int j : tree[p]) {
                    ind[j]--;
                    if (ind[j] == 1) {
                        q.add(j);
                    }
                }
            }
        }
        List<Integer> ans = new ArrayList<>();
        ans.addAll(q);
        return ans;
    }
}