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

https://school.programmers.co.kr/learn/courses/30/lessons/388354

프로그래머스

요즘 너무 알고리즘 위주로 푼 것 같아서 마침 플머에 코드챌린지 문제가 올라왔길래 차례로 풀고 있다. (쉽지 않음)

 

문제

1개 이상의 트리 - 여러 트리가 모인 포레스트가 주어지며, 각 노드는 서로 다른 번호를 가진다.

이때 각 노드는 네 가지 종류 중 하나가 된다:

	노드 번호	자식 노드 개수
홀수 노드	홀수	홀수
짝수 노드	짝수	짝수
역홀수 노드	홀수	짝수
역짝수 노드	짝수	홀수

 

문제에서 구하고자 하는 것은 각 트리에 대해 루트 노드를 설정했을 때, (1)홀짝 트리 개수와 (2)역홀짝 트리 개수가 된다.

이때 각 트리의 정의는:

홀짝 트리	홀수 노드 + 짝수 노드
역홀짝 트리	역홀수 노드 + 역짝수 노드

 

생각해 보자

문제를 읽었을 때, 생각난 논리 흐름은 다음과 같다:

(1)루트 노드를 차례로 회전하면서
(2)각 루트 노드가 어떤 노드인지 확인하고
(3)각 루트 노드의 종류에 따라 홀짝 트리인지 역홀짝 트리인지 확인한다.

이렇게 큰 구조가 잡혔다.

 

다시 각 단계에 대해 구체적으로 생각해 봤다.

(1)루트 노드를 차례로 회전하면서

트리를 구성하고 있는 모든 노드값이 `int[] nodes`로 주어지므로 이에 대해 for문으로 탐색한다.

 

(2)각 루트 노드가 어떤 노드인지 확인하고

앞서 언급했던 네 가지 노드 종류 중 어떤 노드인지 확인해야 한다. 노드 종류 구분을 위해 확인해야 하는 단계를 구체적으로 세워보면,

   - 현재 루트 노드의 번호가 짝수인지 홀수인지

   - 현재 루트 노드의 자식 개수를 구하고, 자식 개수가 짝수인지 홀수인지

 

(3)각 루트 노드의 종류에 따라 홀짝 트리인지 역홀짝 트리인지 확인한다.

• 루트 노드의 번호가 홀수이고 + 자식 개수가 홀수이면 → 홀짝 트리인지 확인
• 루트 노드의 번호가 홀수이고 + 자식 개수가 짝수이면 → 역홀짝 트리인지 확인
• 루트 노드의 번호가 짝수이고 + 자식 개수가 짝수이면 → 홀짝 트리인지 확인
• 루트 노드의 번호가 짝수이고 + 자식 개수가 홀수이면 → 역홀짝 트리인지 확인

 

여기까지 오면 이제 고민이 되는 부분은 자식 노드 개수를 세는 로직과 홀짝 트리/역홀짝 트리 확인을 어떻게 구현할 것인가 된다.

 

먼저 자식 노드 개수를 세는 로직에 대해 생각해 본다.

🚧 자식 노드와 관련해서 주의할 점은 자식 노드(Child Node)와 자손 노드(Descendant Node)를 구분해야 한다는 것이다.
     (나는 처음에 자손 노드를 모조리 세서 자식 노드로 포함시켜 버리는 바람에 어디가 틀린 건지 찾느라 굉장히 오래 고민했다...)

기준 노드와 연결된 노드 개수를 세면 되는데, 현재 그래프(트리)가 무방향으로 이루어져있으므로 부모 노드인 기준 노드를 제외해야 한다.

 

 

그리고 트리 종류를 판별하기 위해서는

• 루트 노드가 홀수/짝수 노드라면 모든 자식 노드도 홀수/짝수 노드여야 하고,
• 루트 노드가 역홀수/역짝수 노드라면 모든 자식 노드도 역홀수/역짝수 노드여야 한다.

따라서 각 노드를 검사할 때마다 똑같은 규칙을 자식 노드에 적용해야 하고, 하나라도 조건에 맞지 않는 노드가 존재한다면 그 트리는 홀짝 트리 또는 역홀짝 트리가 될 수 없다. 결국 이 과정을 생각했을 때 모든 노드가 루트 노드와 같은 유형인지 확인하는 재귀 구조가 된다.

 

그래서 구조를 좀 더 구체적으로 생각해보면,

• 루트 노드가 홀/짝수 노드라면, 현재 트리는 홀짝 트리임을 가정하고, 연결된 모든 노드에 대해 홀/짝수 노드인지 검사한다.
• 루트 노드가 역홀/역짝수 노드라면, 현재 트리는 역홀짝 트리임을 가정하고, 연결된 모든 노드에 대해 역홀/역짝수 노드인지 검사한다.

 

홀/짝수 노드인지 검사하는 로직은

1. 현재 노드 번호의 홀/짝수 여부를 확인하고
2. 현재 노드의 자식 노드 개수를 구한 다음
3. 노드 번호가 홀수면 자식 노드가 홀수인지, 노드 번호가 짝수면 자식 노드 개수가 짝수인지 확인하여
4. 홀수+홀수, 짝수+짝수 조합인지 확인하여, 맞다면 현재 노드의 자식 노드로 이동해 똑같이 반복하고, 아니라면 즉시 실패를 반환한다.

역홀/역짝수 노드인지 확인하는 로직은

1. 현재 노드 번호의 역홀/역짝수 여부를 확인하고
2. 현재 노드의 자식 노드 개수를 구한 다음
3. 노드 번호가 홀수면 자식 노드가 짝수인지, 노드 번호가 짝수면 자식 노드 개수가 홀수인지 확인하여
4. 홀수+짝수, 짝수+홀수 조합인지 확인하여, 맞다면 현재 노드의 자식 노드로 이동해 똑같이 반복하고, 아니라면 즉시 실패를 반환한다.

 

생각한 논리구조를 바탕으로 구현하면

import java.util.List; import java.util.ArrayList;
import java.util.Map; import java.util.HashMap;

class Solution {
    public int[] solution(int[] nodes, int[][] edges) {
        int[] answer = new int[2];
        
        Map<Integer, List<Integer>> forest = new HashMap<>();
        makeForest(forest, edges);
        
        //루트노드 차례로 회전
        for(int root : nodes) {
            int children = countChildren(forest, root, 0, root);
            
            //루트노드가 홀/짝 노드일 경우 -> 계속해서 홀짝인지 확인
            if(isEven(root) == isEven(children)) {
                if(checkOE(forest, root, root)) answer[0]++;
            }
            
            //루트노드가 역홀/역짝 노드일 경우 -> 계속해서 역홀/역짝인지 확인
            else {
                if(checkReversedOE(forest, root, root)) answer[1]++;
            }
        }
        
        return answer;
    }
    
    void makeForest(Map<Integer, List<Integer>> forest, int[][] edges) {
        //무방향 그래프
        for(int[] edge : edges) {
            forest.computeIfAbsent(edge[0], k->new ArrayList<>()).add(edge[1]);
            forest.computeIfAbsent(edge[1], k->new ArrayList<>()).add(edge[0]);
        }
    }
    
    boolean isEven(int num) { return num % 2 == 0; }
    
    int countChildren(Map<Integer, List<Integer>> forest, int curr, int cnt, int prev) {
        if(!forest.containsKey(curr)) return 0; //자식 노드가 없으면 0 리턴
        
        for(int next : forest.get(curr)) {
            if(next == prev) continue;
            cnt++; //직접 연결된 노드만 자식 노드임!!
        }
        
        return cnt;
    }
    
    boolean checkOE(Map<Integer, List<Integer>> forest, int curr, int prev) {
        int children = countChildren(forest, curr, 0, prev);
        
        //자식 노드가 없으면 현재 노드 번호 짝/홀 확인 후 즉시 리턴 
        if(children == 0) return isEven(curr);
        
        //홀수 노드이거나 짝수 노드면 다음 자식 노드로 이동
        if(isEven(curr) == isEven(children)) {
            for(int next : forest.get(curr)) {
                if(next == prev) continue;
                if(!checkOE(forest, next, curr)) return false;
            }
        } else return false; //홀/짝노드가 아니면 실패 
        
        return true;
    }
    
    boolean checkReversedOE(Map<Integer, List<Integer>> forest, int curr, int prev) {
        int children = countChildren(forest, curr, 0, prev);
        
        //자식 노드가 없으면 현재 노드 번호 짝/홀 확인 후 즉시 리턴 
        if(children == 0) return !isEven(curr);
        
        //역홀수 노드이거나 역짝수 노드면 다음 자식 노드로 이동
        if(isEven(curr) != isEven(children)) {
            for(int next : forest.get(curr)) {
                if(next == prev) continue;
                if(!checkReversedOE(forest, next, curr)) return false;
            }
        } else return false; //역홀/짝노드가 아니면 실패
        
        return true;
    }
}

 

 

논리를 구체적으로 세우고 그걸 바탕으로 차근차근 구현하면 풀리는 문제였다. 근데 시험장에서 문제로 만났다면 더 오래 걸렸을 것 같기도..

생각이 막혔던 부분: (1)자식 노드랑 자손 노드를 구분하지 않았던 점.. (2)자식 노드 개수 셀 때 부모 노드(기준 노드)를 제외해야 했던 점