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

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

프로그래머스

 

문제 유형

• 그래프
• 구현

 

문제 난이도

• Lev3

 

문제 분석

1) 주어진 조건

출력값 : [홀짝 트리, 역홀짝 트리] 의 개수
* 홀수 노드 : 노드의 번호도 홀수이고, 자식 노드의 개수도 홀수인 경우
* 짝수 노드 : 노드의 번호가 짝수이고, 자식 노드의 개수도 짝수인 경우
* 역홀수 노드 : 노드의 번호는 홀수인데, 자식 노드의 개수는 짝수인 경우
* 역짝수 노드 : 노드의 번호는 짝수인데, 자식 노드의 개수는 홀수인 경우

2) 내가 생각한 문제 분석

* 홀짝 트리의 경우 모든 리프 노드는 짝수 번호의 리프 노드를 가져야 한다.
* 역홀짝 트리의 경우, 모든 리프 노드는 홀수 번호의 노드를 가져야 한다.
* 만약, root만 다르고 트리의 모양이 동일한 경우는 COUNTING을 어떻게 해줄 것인가 -> 근데 우선 노드의 번호가 달라지면 결과값도 달라질 수 있으므로 다른 케이스로 봐야할 것이다.

 

코드 분석

 

변수 설정

자식 노드에 대한 번호를 저장하기 위해 Node 클래스안에 childs List 배열을 선언해주고, nodeList라는 Node[] 배열에 대해서 인스턴스들을 생성해준다.

map은 노드의 번호와 nodeList에 대한 인덱스를 매칭 시켜주고, count 같은 경우, 자식 노드의 개수가 짝수인지 홀수인지를 파악하기 위해 counting을 해주었다.

해당 counting의 경우, 양방향으로 설정했으므로, 현재 노드의 번호가 root 노드가 아닌 경우는 자신보다 부모 노드의 개수는 1개 빼줘야 하므로 이후 isValid() 함수에서 -1을 해준다. -> isValid() 함수에서 추가 설명

static class Node {
    int weight;
    List<Integer> childs = new ArrayList<>(); // 노드의 번호가 저장된다.

    public Node(int weight) {
        this.weight = weight;
    }
}

static Node[] nodeList;
static Map<Integer, Integer> map, count;


---------------------------------------------------------------------

nodeList = new Node[nodes.length];
map = new HashMap<>();
count = new HashMap<>(); // 자식 노드의 개수가 짝수인지 홀수인지를 파악하기 위해

for(int i = 0; i < nodes.length; i++) {
    nodeList[i] = new Node(nodes[i]);
    map.put(nodes[i], i); // {노드 번호, Node[] 배열의 인덱스}
    count.put(nodes[i], 0);
}

int a, b;
for(int i = 0; i < edges.length; i++) {
    a = edges[i][0];
    b = edges[i][1];

    nodeList[map.get(a)].childs.add(b);
    nodeList[map.get(b)].childs.add(a);

    count.put(a, count.getOrDefault(a, 0) + 1);
    count.put(b, count.getOrDefault(b, 0) + 1);
}

 

 

모든 노드에 대해서 각 노드의 번호를 root라고 가정하고, 홀짝 트리 노드에 대한 검증과 역홀짝 트리에 대한 검증을 진행하였다.

우선 node들의 최대 개수는 400,000개이다. 어차피, root 노드부터 검증을 들어갈 때, 해당 트리가 유효한지부터 검증하고, 유효하지 않은 경우 바로 return 하므로 시간 복잡도에 걸리지 않았다.

for(int i = 0; i < nodes.length; i++) {
    int root = nodes[i]; // 현재 루트 노드의 번호


    Set<Integer> visited = new HashSet<>();


    // 1. 루트 노드가 홀짝 트리인지 검증
    if(isValid(root, root, visited)) {
        // 1-1. 홀짝 트리인지 검증하고, 맞다면 result++;
        if(solve(root, visited)) {
            result[0]++;
        }
    }

    visited = new HashSet<>();

    // 1-2. 역홀짝 트리가 맞는지 검증한다.
    if(!isValid(root, root, visited)) {
        if(reverse(root, visited)) {
            result[1]++;
        }
    }
}

 

 

 

트리에 대한 유효성 검증

 

start에 해당하는 현재 노드의 번호가 홀짝 트리인지, 역홀짝트리인지를 판단하는 메소드이다.

홀짝 트리가 짝수(홀수)번호 -> 짝수(홀수) 개의 자식 노드
역홀짝 트리가 짝수(홀수)번호 -> 홀수(짝수) 개의 자식 노드

 

이므로 홀짝 메소드 == !역홀짝 메소드와 같다.

// 홀짝 트리에 대한 유효성 검증
static boolean isValid(int root, int start, Set<Integer> visited) {
    int cnt = count.get(start);
    if(root != start) cnt--;

    if((start & 1) == 0) {
        // 짝수
        if((cnt & 1) == 0) return true;
        else return false;
    } else {
        // 홀수
        if((cnt & 1) == 1) return true;
        else return false;
    }
}

 

홀짝 트리 판단 여부

Stack과 방문처리 여부를 활용하여 메소드를 구현하였다. 자신과 연결되어 있는 노드에 대하여 방문하지 않은 노드에 대해서 해당 노드가 홀짝 트리에 대한 조건(노드 번호가 짝수일 경우, 자식 노드의 개수도 짝수, 홀수일 경우도 이하 동일)을 만족한다면 홀짝 트리에 대한 counting을 해준다.

static boolean solve(int root, Set<Integer> visited) {
    // 홀짝 트리 여부 확인
    // DFS + memoization
    visited.add(root);

    ArrayDeque<Integer> stk = new ArrayDeque<>();
    stk.push(root);

    while(!stk.isEmpty()) {
        int p = stk.pop();

        for(Integer next : nodeList[map.get(p)].childs) {

            if(visited.contains(next)) continue;

            // 만약 하나라도 홀짝 트리에 위배된다면 불가능
            if(!isValid(root, next, visited)) return false;

            stk.push(next);
            visited.add(next);
        }
    }

    return true;

}

 

 

역홀짝 트리 판단 여부

앞선 홀짝 트리 판단 여부와 내용은 거의 동일하지만, 역홀짝 트리의 판단 여부는 노드 번호가 짝수일 경우는 자식 노드의 개수는 홀수개, 홀수 번호일 경우, 자식 노드의 개수는 짝수 개이므로 isValid() 메소드를 재사용해서 서로 반대되는 경우이므로 !만 바꿔서 판단하여 true일 경우, 역홀짝 트리를 counting 해준다.

static boolean reverse(int root, Set<Integer> visited) {
    // 역홀짝 트리가 맞는지 검증
    // DFS + memoization

    visited.add(root);

    ArrayDeque<Integer> stk = new ArrayDeque<>();
    stk.push(root);

    while(!stk.isEmpty()) {

        int p = stk.pop();

        for(Integer next : nodeList[map.get(p)].childs) {

            if(visited.contains(next)) continue;

            if(isValid(root, next, visited)) return false;

            stk.push(next);
            visited.add(next);
        }   
    }

    return true;

}

 

 

전체 코드

import java.util.*;
import java.io.*;

class Solution {
    static class Node {
        int weight;
        List<Integer> childs = new ArrayList<>(); // 노드의 번호가 저장된다.
        
        public Node(int weight) {
            this.weight = weight;
        }
    }
    
    static Node[] nodeList;
    static Map<Integer, Integer> map, count;
    public int[] solution(int[] nodes, int[][] edges) {
        int[] result = new int[2];
        
        nodeList = new Node[nodes.length];
        map = new HashMap<>();
        count = new HashMap<>(); // 자식 노드의 개수가 짝수인지 홀수인지를 파악하기 위해
        
        for(int i = 0; i < nodes.length; i++) {
            nodeList[i] = new Node(nodes[i]);
            map.put(nodes[i], i); // {노드 번호, Node[] 배열의 인덱스}
            count.put(nodes[i], 0);
        }
        
        int a, b;
        for(int i = 0; i < edges.length; i++) {
            a = edges[i][0];
            b = edges[i][1];
            
            nodeList[map.get(a)].childs.add(b);
            nodeList[map.get(b)].childs.add(a);
            
            count.put(a, count.getOrDefault(a, 0) + 1);
            count.put(b, count.getOrDefault(b, 0) + 1);
        }
        
        for(int i = 0; i < nodes.length; i++) {
            int root = nodes[i]; // 현재 루트 노드의 번호
            
            Set<Integer> visited = new HashSet<>();
            
            
            // 1. 루트 노드가 홀짝 트리인지 검증
            if(isValid(root, root, visited)) {
                // 1-1. 홀짝 트리인지 검증하고, 맞다면 result++;
                if(solve(root, visited)) {
                    result[0]++;
                }
            }
            
            visited = new HashSet<>();
            
            // 1-2. 역홀짝 트리가 맞는지 검증한다.
            if(!isValid(root, root, visited)) {
                if(reverse(root, visited)) {
                    result[1]++;
                }
            }
        }
        
        return result;
        
    }
    
    static boolean solve(int root, Set<Integer> visited) {
        // 홀짝 트리 여부 확인
        // DFS + memoization
        visited.add(root);
        
        ArrayDeque<Integer> stk = new ArrayDeque<>();
        stk.push(root);
        
        while(!stk.isEmpty()) {
            int p = stk.pop();
            
            for(Integer next : nodeList[map.get(p)].childs) {
                
                if(visited.contains(next)) continue;
                
                // 만약 하나라도 홀짝 트리에 위배된다면 불가능
                if(!isValid(root, next, visited)) return false;
                
                stk.push(next);
                visited.add(next);
            }
        }
        
        return true;
            
    }
    
    static boolean reverse(int root, Set<Integer> visited) {
        // 역홀짝 트리가 맞는지 검증
        // DFS + memoization
        
        visited.add(root);
        
        ArrayDeque<Integer> stk = new ArrayDeque<>();
        stk.push(root);
        
        while(!stk.isEmpty()) {
            
            int p = stk.pop();
                        
            for(Integer next : nodeList[map.get(p)].childs) {
                
                if(visited.contains(next)) continue;
                
                if(isValid(root, next, visited)) return false;
                
                stk.push(next);
                visited.add(next);
            }   
        }
        
        return true;
        
    }
    
    // 홀짝 트리에 대한 유효성 검증
    static boolean isValid(int root, int start, Set<Integer> visited) {
        int cnt = count.get(start);
        if(root != start) cnt--;
        
        if((start & 1) == 0) {
            // 짝수
            if((cnt & 1) == 0) return true;
            else return false;
        } else {
            // 홀수
            if((cnt & 1) == 1) return true;
            else return false;
        }
    }
}