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

문제

코딩테스트 연습 - 홀짝트리

알고리즘 문제 연습 카카오톡 친구해요! 프로그래머스 교육 카카오 채널을 만들었어요. 여기를 눌러, 친구 추가를 해주세요. 신규 교육 과정 소식은 물론 다양한 이벤트 소식을 가장 먼저 알려드립니다.

school.programmers.co.kr

문제 정리

요약

• 포레스트가 주어집니다. (루트 노드가 설정되지 않은 1개 이상의 트리의 모음)
• 각 트리에 대해 루트 노드가 설정했을 때 홀짝 트리가 될 수 있는 트리의 개수와 역홀짝 트리가 될 수 있는 트리의 개수를 구하면 됩니다.
• 홀짝 트리
  • 정의: 홀수 노드와 짝수 노드로 이루어져 있습니다.
  • 훌수 노드 ➞ 노드의 번호가 홀수이면서 자식 노드 개수가 홀수 인 것.
  • 짝수 노드 ➞ 노드의 번호가 짝수이면서 자식 노드 개수가 짝수 인 것.
• 역홀짝 트리
  • 정의: 역홀수 노드와 역짝수 노드로 이루어져 있습니다.
  • 역홀수 노드 ➞ 노드의 번호가 홀수이면서 자식 노드 개수가 짝수인 것.
  • 역짝수 노드 ➞ 노드의 번호가 짝수이면서 자식 노드 개수가 홀수인 것.
• 단, 0은 짝수로 봅니다.

입력 조건

• nodes 개수: 1 ~ 400,000
• node 번호: 1 ~ 100,000
  • node 번호는 중복되지 않습니다.
• edges 개수: 1 ~ 1,000,000

출력

홀짝 트리의 개수와 역홀짝 트리의 개수 반환.

---

문제 풀이

1. 단순한 접근

  가장 직관적인 방법으로 각 노드를 루트 노드라고 가정하여 트리를 탐색하는 것입니다. 하지만 노드가 최대 400,000(40만)개이므로 시간복잡도는 O(10¹¹)로 시간 내에 해결 할 수 없습니다.

따라서 루트 노드를 매번 바꾸어 탐색하지 않고도 조건을 판단 할 수 있는 방법이 필요합니다.

2. 노드 상태 변경 규칙 찾기

  여기서 주목할 점은 바로 노드의 자식 개수는 루트 여부에 따라서 홀짝이 변경됩니다. 연결된 노드 수를 degree라고 하면

• 루트 노드 -> 자식 수 = degree
• 일반 노드 -> 자식 수 = degree - 1

즉, 루트 여부에 따라 자식 수의 홀짝이 항상 반전됩니다. 이 성질 때문에 노드의 상태가 다음과 같이 반전됩니다.

루트 노드 O		루트 노드 X
홀수 노드	⟶	역홀수 노드
짝수 노드	⟶	역짝수 노드
역홀수 노드	⟶	홀수 노드
역짝수 노드	⟶	짝수 노드

 모든 노드 상태를 루트 노드를 가정하여 계산했을 때, 실제 루트 노드를 선택하게 되면 다음과 같이 상태가 변경됩니다.

• 루트 노드 -> 상태 유지
• 그 외 모두 -> 상태 반전

3. 결론

루트를 선택하면 루트는 상태가 유지되고 나머지 노드 모두 반전되므로, 전체 트리가 같은 상태를 가지기 위해서는 루트 하나만 다른 상태여야 합니다.

따라서 다음과 같은 결론을 내릴 수 있습니다.

홀짝 트리

1개의 노드만 홀짝 노드이고 나머지는 모두 역홀짝 노드이어야 합니다.

역홀짝 트리

1개의 노드만 역홀짝 노드이고 나머지는 모두 홀짝 노드이어야 합니다.

---

풀이 코드

def solution(nodes, edges):
    # 데이터 전처리
    adj_list = {key: set() for key in nodes}
    
    for a, b in edges:
        # 인접 리스트 구축
        adj_list[a].add(b)
        adj_list[b].add(a)
    
    answer = [0, 0]
    
    # 해 구하기
    visit = {key: False for key in nodes}   # 방문 여부 처리
    
    for key in nodes:
        if visit[key]:
            continue
        
        odd, even = 0, 0
        r_odd, r_even = 0, 0
        
        # 트리 탐색
        visit[key] = True
        to_visit = [key]
        
        while to_visit:
            now_key = to_visit.pop()
            
            # 노드 상태 계산
            if now_key % 2 == 0:
                # 짝수 노드
                if len(adj_list[now_key]) % 2 == 0:
                    even += 1
                # 역짝수 노드
                else:
                    r_even += 1
            else:
                # 홀수 노드
                if len(adj_list[now_key]) % 2 == 1:
                    odd += 1
                # 역홀수 노드
                else:
                    r_odd += 1
            
            # 방문 처리 및 방문 예정 노드 저장
            for next_node in adj_list[now_key]:
                if not visit[next_node]:
                    to_visit.append(next_node)
                    visit[next_node] = True
        
        # 판단
        if odd + even == 1:
            answer[0] += 1
        if r_odd + r_even == 1:
            answer[1] += 1
    
    return answer