[level 3] 홀짝트리 - 388354

문제 링크

성능 요약

메모리: 290 MB, 시간: 718.45 ms

구분

코딩테스트 연습 > 2025 프로그래머스 코드챌린지 1차 예선

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2025년 03월 04일 16:35:14

문제 설명

루트 노드가 설정되지 않은 1개 이상의 트리가 있습니다. 즉, 포레스트가 있습니다.
모든 노드들은 서로 다른 번호를 가지고 있습니다.

각 노드는 홀수 노드, 짝수 노드, 역홀수 노드, 역짝수 노드 중 하나입니다. 각 노드의 정의는 다음과 같으며, 0은 짝수입니다.

• 홀수 노드
  • 노드의 번호가 홀수이며 자식 노드의 개수가 홀수인 노드입니다.
• 짝수 노드
  • 노드의 번호가 짝수이며 자식 노드의 개수가 짝수인 노드입니다.
• 역홀수 노드
  • 노드의 번호가 홀수이며 자식 노드의 개수가 짝수인 노드입니다.
• 역짝수 노드
  • 노드의 번호가 짝수이며 자식 노드의 개수가 홀수인 노드입니다.

당신은 각 트리에 대해 루트 노드를 설정했을 때, 홀짝 트리가 될 수 있는 트리의 개수와 역홀짝 트리가 될 수 있는 트리의 개수를 구하려고 합니다. 각 트리의 정의는 다음과 같습니다.

• 홀짝 트리
  • 홀수 노드와 짝수 노드로만 이루어진 트리입니다.
• 역홀짝 트리
  • 역홀수 노드와 역짝수 노드로만 이루어진 트리입니다.

다음은 트리의 루트 노드를 설정하는 예시입니다.

다음과 같은 트리가 있습니다.

위 트리의 루트 노드를 3번 노드로 설정하게 되면 다음과 같은 형태가 됩니다.

노란색 노드는 홀수 노드 혹은 짝수 노드를 나타내고, 빨간색 노드는 역홀수 노드 혹은 역짝수 노드를 나타냅니다. 이 경우, 모든 노드가 노란색이므로 홀짝 트리가 됩니다.

이 트리의 루트 노드를 6번 노드로 설정하게 되면 다음과 같은 형태가 되어 홀짝 트리 혹은 역홀짝 트리가 될 수 없습니다.

이와 마찬가지로 다른 노드를 루트 노드로 설정하는 경우에는 홀짝 트리 혹은 역홀짝 트리가 될 수 없습니다.
3번 노드를 루트 노드로 설정하는 경우에만 홀짝 트리가 될 수 있습니다. 따라서 위 트리는 홀짝 트리가 될 수 있는 트리입니다.

다음은 어떤 노드를 루트 노드로 설정하더라도 홀짝 트리 혹은 역홀짝 트리가 될 수 없는 트리입니다.

즉, 트리는 어떤 노드를 루트 노드로 설정하냐에 따라 홀짝 트리 혹은 역홀짝 트리가 될 수 있습니다. 경우에 따라 하나의 트리가 홀짝 트리와 역홀짝 트리 두 가지 모두 될 수 있거나 두 가지 모두 될 수 없을 수도 있습니다.

포레스트에 존재하는 노드들의 번호를 담은 1차원 정수 배열 nodes, 포레스트에 존재하는 간선들의 정보를 담은 2차원 정수 배열 edges가 매개변수로 주어집니다. 이때, 홀짝 트리가 될 수 있는 트리의 개수와 역홀짝 트리가 될 수 있는 트리의 개수를 1차원 정수 배열에 순서대로 담아 return 하도록 solution 함수를 완성해 주세요.

---

제한사항

• 1 ≤ nodes의 길이 ≤ 400,000
  • 1 ≤ nodes의 원소 ≤ 1,000,000
  • nodes의 원소는 중복되지 않습니다.
• 1 ≤ edges의 길이 ≤ 1,000,000
  • edges의 원소는 [a, b] 형태의 1차원 정수 배열이며, a번 노드와 b번 노드 사이에 무방향 간선이 존재한다는 것을 의미합니다.
  • a, b는 nodes에 존재하는 원소이며 서로 다릅니다.
• 포레스트인 경우만 입력으로 주어집니다.

---

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

그룹	총점	추가 제한 사항
#1	10%	하나의 트리만 주어집니다. nodes의 길이 ≤ 1,000, edges의 길이 ≤ 1,000
#2	10%	nodes의 길이 ≤ 1,000, edges의 길이 ≤ 1,000
#3	30%	하나의 트리만 주어집니다.
#4	50%	추가 제한 사항 없음

---

입출력 예

nodes	edges	result
[11, 9, 3, 2, 4, 6]	[[9, 11], [2, 3], [6, 3], [3, 4]]	[1, 0]
[9, 15, 14, 7, 6, 1, 2, 4, 5, 11, 8, 10]	[[5, 14], [1, 4], [9, 11], [2, 15], [2, 5], [9, 7], [8, 1], [6, 4]]	[2, 1]

---

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

홀짝 트리가 될 수 있는 트리가 하나 존재하고, 역홀짝 트리가 될 수 있는 트리는 존재하지 않습니다.
따라서 [1, 0]을 return 해야 합니다.

입출력 예 #2

주어진 포레스트를 그림으로 나타내면 다음과 같습니다.

1, 3번째 트리는 각각 10번 노드, 4번 노드를 루트 노드로 설정하면 홀짝 트리가 될 수 있고, 2번째 트리는 9번 노드를 루트 노드로 설정하면 역홀짝 트리가 될 수 있습니다.
4번째 트리는 어떤 노드를 루트 노드로 설정해도 홀짝 트리 혹은 역홀짝 트리가 될 수 없습니다.
따라서 [2, 1]을 return 해야 합니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

문제풀이

코드

import java.util.*;

class Solution {
    static int[] p;
    static ArrayList<Integer>[] board;
    static Map<Integer, Integer> p_visited = new HashMap<>();
    public int[] solution(int[] nodes, int[][] edges) {
        /*
            트리 그룹으로 나누고 각 그룹마다 홀짝트리 or 역홀짝트리 여부 보기
            -> 홀짝이 1개면 g2++ , 역홀짝이 1개면 g1++
        */
        
        int g1=0, g2=0; // g1 : 홀짝트리 수, g2 : 역홀짝트리 수
        int s = 0;
        for(int n : nodes){
            if(s < n) s = n;
        }
        
        p = new int[s + 1];
        for(int i=0; i<nodes.length; i++){
            p[nodes[i]] = nodes[i];
        }
        
        board = new ArrayList[s+1];
        for(int i=1; i< s + 1; i++){
            board[i] = new ArrayList<>();
        }
        
        for(int[] e : edges){
            board[e[0]].add(e[1]);
            board[e[1]].add(e[0]);
        }
        
        for(int[] e : edges){
            union(find(e[0]), find(e[1]));
        }
        
        for(int i=0; i<nodes.length; i++){
            int node = find(nodes[i]);
            if(!p_visited.containsKey(node)){
                p_visited.put(node, 0);
                
                int[] tmp = bfs(node);
                if(tmp[0] == 1) g1++;
                if (tmp[1] == 1) g2++;
            }
        }
        
        int[] res = new int[]{g1, g2};
        return res;
    }
    
    private void union(int x, int y){
        int px = find(x);
        int py = find(y);
        if(px <= py) p[py] = px;
        else p[px] = py;
        return;
    }
    
    private int find(int x){
        if(p[x] != x) return p[x] = find(p[x]);
        return x;
    }
    
    private int[] bfs(int node){
        int tmp_g1=0, tmp_g2=0; // 홀짝 and 역홀짝 개수세기
        
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        queue.offer(node);
        visited.add(node);
        
        while(!queue.isEmpty()){
            int curr = queue.poll();
            int currSize = board[curr].size();
            
            if((curr + currSize) % 2 == 0) tmp_g1++;
            else tmp_g2++;
            
            for(int next : board[curr]){
                if(visited.add(next)){
                    queue.offer(next);
                }
            }
        }

        return new int[]{tmp_g1, tmp_g2};
    }
}