[2025 프로그래머스 코드챌린지 1차 예선] - 홀짝트리 (Java)

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

프로그래머스

 

코드 :

import java.util.*;

class Solution {
    
    List<Integer>[] adj;
    
    Set<Integer> visited = new HashSet<>(); // 방문체크
    Map<Integer, List<Integer>> groupMap = new HashMap<>(); // groupNo -> nodes  

    public static final int FORWARD_TREE = 0; // 홀짝트리
    public static final int REVERSE_TREE = 1; // 역홀짝트리
    
    int yellow = 0;
    int red = 0;
    
    public int[] solution(int[] nodes, int[][] edges) {
        int[] answer = new int[2];
        int n = 1_000_000;
        
        adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();
        
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
        
        for (int root : nodes) {
            yellow = 0; red = 0;
            searchGroup(root);
            
            // yello 1개 -> 모두 red로 만들 수 있음 -> 역홀짝
            if (yellow == 1) {
                answer[REVERSE_TREE]++;
            }
            
            // red 1개 -> 모두 yellow -> 홀짝
            if (red == 1) {
                answer[FORWARD_TREE]++;
            }
        }
        
        return answer;
    }
    // 해당 노드가 속한 그룹의 색깔을 카운트
    private void searchGroup(int now) {
        if (visited.contains(now)) {
            return;
        }
        visited.add(now);
        
        // 루트가 아닐때의 각 노드 색깔
        boolean isYellowWhenNotRoot = (now % 2 == (adj[now].size() - 1) % 2);
                
        if (isYellowWhenNotRoot) yellow++;
        else red++;
         
        for (int next : adj[now]) {
            searchGroup(next);    
        }
    } 
}

풀이 :

• 문제의 예시를 참고하여 홀짝노드는 Y(Yellow), 역홀짝노드는 R(Red)로 표현하겠습니다. 트리(그룹)별로 모든 노드의 색이 Y 혹은 R인 경우를 찾아야합니다.
• 특정 노드를 루트노드로 지정한다면, 값은 그대로지만 자식노드가 +1 됩니다.
  • (노드 -> 루트노드)로 변경 시, 원래 홀짝 노드였다면 역홀짝으로(Y->R), 원래 역홀짝이었다면 홀짝(R->Y)로 변경됩니다.
  • 그 반대도 같습니다. (루트노드 -> 노드)로 변경시 Y->R, R->Y로 바뀝니다.
• 그렇기때문에, 그룹별로 "모든 노드가 루트아닌 노드라고 가정"하고, 각 노드가 Y인지 R인지 판별했을 때, 딱 하나의 노드만 다른 색이라면, 해당 노드를 루트 노드로 지정했을때 모든 노드의 색깔이 같아집니다.
  • ex) 특정 그룹의 노드 색깔(루트 아닌 상태) = [Y, R, R, R, R];
  • 여기서 첫번째 노드를 루트로 지정하면, [R, R, R, R, R]이 됩니다.
• 주어진 입력에 nodes의 길이가 1일때, 2일때를 주의해야합니다.

요약

• 1) 인접리스트 초기화
• 2) 그룹별로 "모든 노드가 루트아닌 노드라고 가정"하고, 해당 그룹의  색깔이 Y인 노드 개수(yellow), R인 노드 개수(red)를 카운트
• 3) 1개만 다른 색깔인 경우, 혼자 다른 색깔을 가진 노드를 루트로 지정하면 홀짝/역홀짝 중 하나가 되므로 알맞게 카운트해준다.