문제 링크

성능 요약

메모리: 253 MB, 시간: 749.80 ms

구분

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

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2025년 02월 20일 23:23:07

문제 설명

루트 노드가 설정되지 않은 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

풀이

느낀점

• 조금 복잡해보이지만, 잘 정리하면 풀만한 문제같다.
• 첫 제출에서 시간초과가 2/54 나왔는데, dfs중단용 flag를 설정했더니 해결됐다.

설계 : 20분

• 인접 노드 정보와 트리 우두머리 정보를 담은 노드 클래스를 정의한다.
• 정의한 노드 클래스의 배열을 생성한다. 길이는 1_000_001이다. (노드 번호로 접근하기 위해)
• 모든 노드를 순회하며 배열에서 유효한 노드들을 초기화 한다. 동시에 모든 노드를 트리 목록에 추가한다.
• 간선 정보를 순회하며 각 노드에 인접 노드 정보를 추가하고, union/find를 사용해 각 트리의 우두머리만 트리 목록에 남긴다.
• 모든 노드를 다시 순회하며 각 노드를 루트로 했을때, 속한 트리가 홀짝 또는 역홀짝 트리가 되는지 확인한다.
  • 시작 노드의 홀짝/역홀짝 여부 확인(boolean)
  • 시작 노드가 속한 트리의 우두머리를 찾아 시작노드의 유형에 맞는 트리로 확인된 적이 있는지 체크(Set holjjak, yeok)
  • 아직 확인되지 않았으면 dfs 순회하여 속한 트리의 모든 모드가 시작노드와 같은 유형의 노드라면 해당 유형트리에 목록 추가

코드(Java)

• 구현 시간: 80분

import java.util.*;
import java.lang.*;

class Solution {
    
    static Node[] ns;
    static Set<Integer> trees;
    static Set<Integer> holjjak;
    static Set<Integer> yeok;
    static boolean flag;
    public int[] solution(int[] nodes, int[][] edges) {
        ns = new Node[1_000_001];
        holjjak = new HashSet<>();
        yeok = new HashSet<>();
        trees = new HashSet<>();
        
        // 노드 초기화, 트리 초기화
        for (int n : nodes) {
            ns[n] = new Node(n);
            trees.add(n);
        }
        
        // 간선 입력, 트리 구분
        for (int[] e : edges) {
            ns[e[0]].child.add(e[1]);
            ns[e[1]].child.add(e[0]);
            
            union(findSet(e[0]), findSet(e[1]));
        }
        
        // 모든 노드에 대해 자신이 루트일 때 홀짝 트리 또는 역홀짝 트리가 되는지 확인 
        // 속한 트리가 이미 홀짝/역홀짝 확인이 됐다면 중복 확인 안함
        for (int n : nodes) {
            // 자신이 루트라면 홀짝인지 역홀짝인지
            boolean isHol = Math.abs(n - ns[n].child.size()) % 2 == 0;
            
            // 트리를 구분하는 우두머리 노드를 구해서 이미 확인됐는지 확인 후 아니라면 순회 시작
            int head = findSet(n);
            if ((isHol && !holjjak.contains(head))      // 자신이 홀짝노드이고 홀짝 트리에 목록에 아직 없는지
                || (!isHol && !yeok.contains(head))) {  // 자신이 역홀짝 노드이고 역홀짝 트리 목록에 아직 없는지
                
                flag = true;    // flag 초기화(dfs 순회중 하나라도 false가 나오면 순회 중단)
                // dfs에서 최종 true가 반환된다는 것은 모두 같은 종류의 노드라는 것(홀짝 또는 역홀짝)
                if (dfs(0, n, isHol)) {
                    if (isHol) holjjak.add(head);
                    else yeok.add(head);
                };
            }
        }
        
        return new int[] {holjjak.size(), yeok.size()};
    }
    
    private static boolean dfs(int before, int node, boolean isHol) {
        // 순회 중 이미 다른 유형의 노드가 나왔거나, 내가 다른 유형의 노드인 경우 리턴
        if (!flag || (before != 0 
            && (Math.abs(node - (ns[node].child.size() - 1)) % 2 == 0) != isHol)) return false;
        
        for (int next : ns[node].child) {
            if (next == before) continue;
            
            if (!dfs(node, next, isHol)) {
                flag = false;
                break;
            }
        }
        
        return flag;
    }
    
    private static int findSet(int x) {
        if (x == ns[x].p) return x;
        return ns[x].p = findSet(ns[x].p);
    }
    
    private static void union(int x, int y) {
        ns[x].p = y;
        trees.remove(x);
    }
}

class Node {
    List<Integer> child;
    int p;
    
    Node (int p) {
        child = new ArrayList<>();
        this.p = p;
    }
}