[Programmers] 등대

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

프로그래머스

 

노드 수는 N개이고 간선 수는 N - 1개이므로 트리를 연상할 수 있는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 우선, 리프 노드에 속하는 등대를 점등하는 것보다 해당 등대에 연결된 등대를 점등하는 것이 낫다고 그리디 하게 접근했습니다.

1.1 정리하자면 리프 노드에 속하는 등대는 점등되는 일이 없습니다.

2. 이에 따라 리프 노드를 제외한 노드들 즉, 두 개 이상 등대에 연결된 등대가 트리의 루트 노드 후보군에 오릅니다.

3. 2번에서 도출해 낸 노드들 중 하나를 루트 노드로 삼아 트리를 구성하고 재귀함수 func를 호출합니다.

3.1 3번에서 호출한 func 함수는 연결된 서브 트리들을 재귀 호출하여 아래와 같이 진행합니다.

3.1.1 1번 원칙에 따라 리프 노드는 점등 X

3.1.2 리프 노드에 연결된 노드는 점등

3.1.3 서브 트리 루트 노드 기준 자식 노드들이 모두 리프 노드가 아닌데 하나라도 점등되어 있지 않을 경우 서브 트리의 루트 노드 점등

3.2 재귀 함수는 스택 구조이고 최하위 서브 트리부터 호출되는 역순 구조이므로 자식 노드의 자식 노드들 중 하나라도 점등되어 있지 않을 경우 자식 노드가 연결점 역할을 수행해야 하므로 자식 노드를 점등해야 합니다. (3.1.3에서 서브 트리의 루트 노드를 점등하는 이유)

4. 3번에서 점등한 등대 수를 반환합니다.

 

 

개발환경: Programmers IDE 

 

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