그래프알고리즘 - minium height trees
리트코드 310번 minimum height trees, 그래프 알고리즘 문제
트리가 주어질 때 최소자식래밸을 가지는 루트노드를 모드 찾는다.
ex1)
위와 같은 트리에서, 최소 자식레벨(2)을 가지는 루트노드는 1
ex2)
위와 같은 트리에선, 최소 자식래밸을(2)를 가지는 루트노드는 3,4. 나머지 노드가 루트노드가 되면 래밸 3이상을 가지게 된다.
풀이
이 문제의 핵심은 leaf노드들 부터 하나씩 없애 주는 것이다.
그렇다면 리프노드는 어떻게 알 수 있는가?
바로 모든 노드들에 대해서 연결된 노드의 개수를 저장하는 리스트(indegree)를 만들고, 연결된 노드가 1이 leaf노드가 된다.
이렇게 하나씩 없애주다가 마지막으로 삭제되는 노드들이 정답노드가 된다.
따라서 풀이를 정리하면 다음과 같다.
[풀이]
1. 연결노드(indegree)가 1개인 노드(=leaf node)를 찾고 해당 노드를 삭제(indegree값 -1)한다.
2. 삭제한 리프노드와 연결된 노드들의 indegree값을 하나씩 줄여준다.
3. 1,2를 반복한다.
4. 마지막으로 삭제된 노드를 반환한다.
[주의사항]
마지막으로 삭제된 노드를 찾을 때, indegree값을 -1 해주는 과정에서 마지막 삭제된 노드가 "[풀이] 1"에서 -1이 될수도 있고, "[풀이] 2" 에서 -1이 될 수도 있다. 이 떄문에 삭제노드 리스트(tempRemoveNode)를 하나더 관리해서 해당 노드가 1에서 삭제되었는지, 2에서 삭제되었는지를 확인해줘야 한다
예를 들어
ex1)의 경우 1의 인접노드 0,2,3이 한번에 없어지면서 indegree[1]을 0으로 만든다. => "[풀이] 2"에서 0이 됨
ex2)의 경우 4,3의 인접노드 5,0,1,2가 삭제되면서 indegree[4,3]을 1로 만들고 그다음 반복에서 0이 된다 => "[풀이] 1"에서 0이 됨
package graph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class LC_310_minimum_height_trees {
static class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
int[] inDegree = new int[n];
// int[][] adjacent = new int[n][n];
List<Integer>[] graph = new ArrayList[n];
for (int i=0; i<n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] edge : edges) {
int node1 = edge[0];
int node2 = edge[1];
inDegree[node1]+=1;
inDegree[node2]+=1;
graph[node1].add(node2);
graph[node2].add(node1);
}
List<Integer> finalAns = new ArrayList<>();
List<Integer> ans = new ArrayList<>();
int[] removedNode = new int[n];
while (true) {
// leaf노드 제거
for (int i=0; i<n; i++) {
if (inDegree[i]==1) {
inDegree[i]-=1;
ans.add(i);
removedNode[i]=1;
}
}
if (ans.isEmpty()) {
// System.out.println(Arrays.toString(removedNode));
List<Integer> tempRemoveNode = new ArrayList<>();
for (int i=0; i<n; i++) {
if (removedNode[i]==0) {
tempRemoveNode.add(i);
}
}
// 마지막 정답노드가 어디에서 삭제된지 확인한다.
if (!tempRemoveNode.isEmpty()) {
return tempRemoveNode;
} else {
return finalAns;
}
} else {
for (int removeEdge : ans) {
for (int adjNode : graph[removeEdge]) {
inDegree[adjNode]-=1;
}
}
finalAns = new ArrayList<>(ans);
ans.clear();
}
}
}
}
public static void main(String[] args) {
LC_310_minimum_height_trees.Solution sol = new LC_310_minimum_height_trees.Solution();
System.out.println(sol.findMinHeightTrees(6, new int[][]{{3,0},{3,1},{3,2},{3,4},{5,4}}));
}
}
오답
오답1. 메모리 초과
인접행렬로 연결여부를 확인하고자 했다. 즉 n*n행렬을 할당하였는데 이는 메모리를 초과한다. 따라서 graph list를 이용해 해당 노드에 연결된 노드들을 저장했다.
오답2. 시간 초과
리프 노드들을 하나씩 삭제할 때 indegree를 -1씩 해주고, 연결상태도 최신화 해주기 위해서 graph를 계속해서 업데이트 해줬다.
} else {
for (int removeEdge : ans) {
for (int j=0; j<n; j++) {
if (graph[removeEdge].contains(j)) {
graph[removeEdge].remove(Integer.valueOf(j));
graph[j].remove(Integer.valueOf(removeEdge));
inDegree[j]-=1;
}
}
}이 부분 때문에 시간초과가 되었는데, 사실 이 문제에서는 leaf노드를 찾기위해 indegree만 업데이트 해주면 되기 떄문에 굳이 graph를 최신화 시켜줄 필요가 없다.
따라서 최종답안으로 아래와 같이 indegree만 관리해주는 방법으로 수정하였다.
} else {
for (int removeEdge : ans) {
for (int adjNode : graph[removeEdge]) {
inDegree[adjNode]-=1;
}
}