[프로그래머스][Java] 홀짝트리

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

프로그래머스

 

요즘 알고리즘 풀이는 거의 안 올렸는데... 푸는데 거의 하루 다 써서.... 나에게는 생각보다 어렵기도 했고... 풀이들이 별로 없는 것 같아?
자세한 설명 버전으로 남겨본다~

 

1. 생각의 흐름

일단 node의 길이가 400,000(40만)이라 나와있다.

따라서 모든 노드를 방문하면서, 해당 노드를 Root로 생각하고 BFS를 타면서서 트리를 확인하려면....
최악의 경우 40만 x 40만 = 160,000,000,000 으로 절대 시간안에 풀 수 없을 거란 생각은 들었다.

 

그러면, N^2으로는 안되구, NlogN이나, N안에 끝내야 하는데....

일단 N으로 끝내려면 Tree탐색을 한 번 하고 판단할 수 있어야 한다고 생각했다.

 

문제는... 그다음부터 Tree를 어떻게 파악 하느냐가 문제인데....

핵심은 Tree에서의 동일한 노드가 Root가 정해진 경우와, Root가 아직 안정해진 경우에 따라서 상태가 바뀐다는 점 이다.

 

다음 문제의 예시 1번을 살펴보자.

 

아직 어떠한 노드를 Root로 잡지 않은 상황에서 각각을 생각하면 다음과 같다.

node 2, 4, 6 : 역짝수 노드

node 3 : 홀수 노드

 

노드 3번을 Root로 잡은 상황에서 각각을 생각하면 다음과 같이 변한다~!

node 2, 4, 6 : 짝수 노드

node 3 : 홀수 노드

 

보았는가? 노드 3번을 Root로 생각한 순간 나머지 노드들(2, 4, 6)의 경우 자기가 갖고 있는 간선 중 하나를 부모 쪽을 향하도록 해야 하기 때문에 자신의 상태가 반전이 되는 것이다~

 

Root가 설정되는 순간, Root는 상태가 유지되고, 나머지 노드들의 상태가 변경되는 것 이다!

 

즉, 다음과 같은 특징이 있는 것이다.

Root 미정       Root정해짐
홀수노드     ->  역홀수 노드
짝수노드     ->  역짝수 노드
역홀수노드    ->  홀수노드
역짝수노드    ->  짝수노드 // 위 그림에서의 예시 케이스

여기까지 생각하면 끝났다!

 

Tree를 만드는 것은 union-find를 활용하여 각 Tree마다 Group을 만들어 준다.

노드모음(2, 3, 4, 6) - Group1

노드모음(9, 11) - Group2

 

이후 각 Group마다 TreeInfo를 만들어, 다음과 같은 정보를 구한다.

public class TreeInfo {
    public int oddNode;
    public int evenNode;
    public int reverseOddNode;
    public int reverseEvenNode;
    // 생략...
}

 

이후 다음과 같이 (홀수노드가 단 1개 or 짝수노드가 단 1개)인 경우

-> 해당 노드를 Root로 정하면 나머지 노드들이 홀짝노드로 상태가 변경 -> 홀짝트리가 될 수 있고.

 

이후 다음과 같이 (역홀수노드가 단 1개 or 역짝수노드가 단 1개)인 경우

-> 해당 노드를 Root로 정하면 나머지 노드들이 역홀짝노드로 상태가 변경 -> 역홀짝트리가 될수 있다.

public boolean isTree() {
    if((oddNode == 1 && evenNode == 0) || (oddNode == 0 && evenNode == 1)) {
        return true;
    }

    return false;
}

public boolean isReverseTree() {
    if((reverseOddNode == 1 && reverseEvenNode == 0) || (reverseOddNode == 0 && reverseEvenNode == 1)) {
        return true;
    }

    return false;
}

 

 

2. 나의 코드

import java.util.*;

class Solution {
    
    private int[] inDegree;
    private int[] parent;
    
    public int[] solution(int[] nodes, int[][] edges) {
        int[] answer = {};
        
        int lastNode = 0;
        for(int node : nodes) {
            lastNode = Math.max(lastNode, node);
        }
        
        inDegree = new int[lastNode + 1];
        parent = new int[lastNode + 1];
        for(int i = 1; i <= lastNode; i++) {
            parent[i] = i;
        }
        
        for(int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            inDegree[a]++;
            inDegree[b]++;
            merge(a, b);
        }
        
        Map<Integer, TreeInfo> MAP = new HashMap();
        for(int node : nodes) {
            int group = find(node);
            
            TreeInfo t = MAP.getOrDefault(group, new TreeInfo());
            
            if((node % 2 == 0) && (inDegree[node] % 2 == 0)) {
                t.evenNode++;
            } else if((node % 2 == 1) && (inDegree[node] % 2 == 1)) {
                t.oddNode++;
            } else if((node % 2 == 0) && (inDegree[node] % 2 == 1)) {
                t.reverseEvenNode++;
            } else if((node % 2 == 1) && (inDegree[node] % 2 == 0)) {
                t.reverseOddNode++;
            }
            
            MAP.put(group, t);
        }
        
        int tree = 0;
        int rTree = 0;
        for(TreeInfo treeInfo : MAP.values()) {
            if(treeInfo.isTree()) {
                tree++;
            }
            
            if(treeInfo.isReverseTree()) {
                rTree++;
            }    
        }
        
        return new int[]{tree, rTree};
    }
               
    public class TreeInfo {
        public int oddNode;
        public int evenNode;
        public int reverseOddNode;
        public int reverseEvenNode;
        
        public TreeInfo() {
            this.oddNode = 0;
            this.evenNode = 0;
            this.reverseOddNode = 0;
            this.reverseEvenNode = 0;
        }
        
        public boolean isTree() {
            if((oddNode == 1 && evenNode == 0) || (oddNode == 0 && evenNode == 1)) {
                return true;
            }
            
            return false;
        }
        
        public boolean isReverseTree() {
            if((reverseOddNode == 1 && reverseEvenNode == 0) || (reverseOddNode == 0 && reverseEvenNode == 1)) {
                return true;
            }
            
            return false;
        }
    }
    
    public int find(int num) {
        if(parent[num] == num) return num;
        return parent[num] = find(parent[num]);
    }
    
    public void merge(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b) {
            parent[b] = a;
        }
    }
}