[Algorithm] 홀짝트리

목차

---

1. 문제 설명

2. 접근 방식

3. 코드

 

 

 

 

 

1. 문제 설명

---

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

프로그래머스

 

문제에는 각 노드에 대한 정의가 나와있다.

모든 노드는 홀수 노드, 짝수 노드, 역홀수 노드, 역짝수 노드 중 하나이며 홀짝 트리와 역홀짝 트리는 아래의 노드로만 이루어진 트리를 의미한다. 

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

 

 

 

 

2. 접근 방식

---

문제에서 주어진 트리는 루트 노드가 설정되어 있지 않다. 

루트 노드와 루트 노드가 아닌 일반 노드는 어떤 차이점이 있을까?
.
.
바로 자식 수에서 차이가 드러난다. 

 

 

왼쪽 트리는 루트가 2이다. 

이때 루트 2는 자식 3을 가지므로 자식의 개수는 1개이다. 

 

반면 오른쪽 트리는 루트가 6이다. 

이때 리프 2는 3을 부모로 갖기 때문에 자식의 개수는 0개가 된다. 

 

즉, 루트 노드는 간선의 개수만큼 자식 수를 갖는다.

하지만 루트가 아닌 일반 노드는 (간선의 개수 - 1) 만큼 자식 수를 갖게 된다.

 

루트 노드 자식 수	루트가 아닌 노드의 자식 수
간선의 개수	간선의 개수 - 1

 

 

 

 

이 그래프는 어떤 트리인가?

노드 숫자	자식 수	노드 판별
3 (홀수)	3 (홀수)	홀수 노드
2 (짝수)	0 (짝수)	짝수 노드
4 (짝수)	0 (짝수)	짝수 노드
6 (짝수)	0 (짝수)	짝수 노드

 

 

0은 짝수로 취급한다. 

문제 속 규칙을 따라 3은 홀수 노드, 2 ~ 6은 짝수 노드로 [ 홀수 노드와 짝수 노드로만 이루어진 ] 홀짝 트리가 된다. 

 

---

 

우리는 자식 수로 새로운 관계를 도출해낼 수 있다. 

일반 노드를 루트 노드로 만든다면, 일반 노드일 때의 자식 수 + 1 인 값을 자식 수로 갖게 된다. 

일반 노드일 때는 연결은 되어있으나 부모로 삼았던 노드를 자식 노드로 만들었기 때문이다. 

 

그럼 노드의 색깔도 변화한다. 

일반 노드일때 노란색이였다면, 자식 수가 변화하면서 빨간색이 된다. 

 

반대의 경우도 성립한다. 

일반 노드일 때 빨간색이였다면, 자식 수가 변환하면서 노란색이 된다. 

 

---

자, 그럼 모든 노드를 루트가 아닌 일반 노드라고 가정해보자. ⭐⭐⭐

 

Q. 노란색이 1개, 나머지는 빨간색 노드로 이루어져 있다면 무슨 트리가 될까?

노란색인 노드를 루트로 올리면 빨간색 노드가 된다. (자식 수가 변화하니까)

그러면 모든 노드가 빨간색이 되면서 역홀짝 트리가 된다. 

 

Q. 빨간색 1개, 나머지는 노란색 노드로 이루어져 있다면 무슨 트리가 될까?

빨간색인 노드를 루트로 올리면 노란색 노드가 된다. (자식 수가 변화하니까)
그러면 모든 노드가 노란색이 되면서 홀짝 트리가 된다. 

 

이제 로직을 코드로 구현해보자. 

 

 

 

3. 코드

---

import java.util.*;

class Solution {
    public static Map<Integer, List<Integer>> graph;
    public static Set<Integer> visited;
    
    public int[] solution(int[] nodes, int[][] edges) {
        graph = new HashMap<>();
        visited = new HashSet<>();
        
        int[] answer = new int[2];
        
        // 1. graph 정보 기록
        for(int n : nodes) {
            graph.put(n, new ArrayList<>());
        }
        
        for(int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }                                    
        
        // 2. 트리 검사
        for(int n : nodes) {
            if(!visited.contains(n)) {  
                int[] color = dfs(n);
                
                if(color[0] == 1) answer[1]++;
                if(color[1] == 1) answer[0]++;   
            }           
        }
        
        return answer;
    }
    
    public static int[] dfs(int start) {      
       int yellow = 0;
       int red = 0;
        
       visited.add(start);
       
       boolean isYellow = (start % 2 == (graph.get(start).size() - 1) % 2);
       if(isYellow) yellow++;
       else red++;
        
       for(int n : graph.get(start)) {
           if(!visited.contains(n)) {
               int[] child = dfs(n);
               
               yellow += child[0];
               red += child[1];
           }
       }
        
       return new int[]{ yellow, red };
    }
}

 

① 특정 노드가 속한 트리 속에서 노드의 색깔을 구분하고

② 노드의 개수로 홀짝 트리 / 역홀짝 트리 여부를 검사한다.

 

 

nodes, edges의 길이를 보라...

그래프 문제를 풀 때 애용하는 리스트 배열은 nodes 원소가 1 ~ 1,000,000이니 비효율적이므로

간선 정보를 저장하는 graph는 Map으로 만드는 편이 좋다고 판단했다. 

+ 더불어 방문 배열도 boolean 보다는 Set 이 최적화하기 용이하다고 생각했다. 

 

public static Map<Integer, List<Integer>> graph;
public static Set<Integer> visited;
    
public int[] solution(int[] nodes, int[][] edges) {
    graph = new HashMap<>();
    visited = new HashSet<>();

    int[] answer = new int[2];

    // 1. graph 정보 기록
    for(int n : nodes) {
        graph.put(n, new ArrayList<>());
    }

    for(int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
    } 
}

 

graph 해시맵을 초기화한 뒤

입력받은 edges를 순회하며 양방향 간선을 저장해주었다. 

 

for(int n : nodes) {
    if(!visited.contains(n)) {  
        int[] color = dfs(n);

        if(color[0] == 1) answer[1]++;
        if(color[1] == 1) answer[0]++;   
    }           
}

 

다음은 트리 검사다. 

방문하지 않은 노드라면, dfs로 트리 속 노드들 중 yellow와 red의 개수를 센다.

 

yellow = 1 ) 해당 노드를 루트 노드로 올리면 all RED가 된다. → 역홀짝 트리

red = 1 ) 해당 노드를 루트 노드로 올리면 all YELLOW가 된다. → 홀짝 트리

 

public static int[] dfs(int start) {      
   int yellow = 0;
   int red = 0;

   visited.add(start);

   boolean isYellow = (start % 2 == (graph.get(start).size() - 1) % 2);
   if(isYellow) yellow++;
   else red++;

   for(int n : graph.get(start)) {
       if(!visited.contains(n)) {
           int[] child = dfs(n);

           yellow += child[0];
           red += child[1];
       }
   }

   return new int[]{ yellow, red };
}

 

dfs로는 위에 언급한 것처럼 yellow, red 노드의 개수를 센다.

노드의 숫자와 자식 수의 홀짝 여부를 비교하여 그 결과가 같다면 홀수 노드 또는 짝수 노드가 되어 yellow++

그렇지 않은 경우엔 역홀수 노드 또는 역짝수 노드가 되어 red++ 해준다.