[Programmers] 홀짝트리

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/388354

프로그래머스

 

Union Find 알고리즘 문제였습니다.

 

알고리즘은 다음과 같습니다.

1. 각 노드에 연결된 간선의 개수인 degree를 기록하고 간선 정보를 이용해 각 노드들이 어떤 트리에 속하는지 파악합니다.

 

2. 각 노드가 홀짝 트리 또는 역홀짝 트리의 루트로 선택될 수 있는지 확인 후, 두 그룹으로 분류합니다.

• (node % 2) == (degree % 2) → 루트로 쓰일 수 있음
• (node % 2) != (degree % 2) → 루트로 쓰일 수 없음

 

3. 홀짝 트리와 역홀짝 트리의 개수를 구합니다.

• 홀짝 트리: 트리 내에 루트로 선택 가능한 노드가 오직 하나
• 역홀짝 트리: 트리 내에 비루트 그룹이 오직 하나

 

 

개발환경: Programmers IDE   

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~