[프로그래머스] 등대

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/133500

문제 풀이

• 트리를 이용한 DFS를 이용하여 풀이하였다.
• 우선 전체 노드 연결 상태를 루트가 1인 트리라고 생각한다.
• 간선의 개수가 n-1이며, 모든 노드가 연결되어 있으므로 해당 트리는 사이클이 존재하지 않는다.
  (DFS를 진행하더라도 노드가 중복되지 않는다.)
• DFS 진행은 다음과 같다.

  //return 1 : 해당 노드는 불을 키지 않음
  //return 0 : 해당 노드는 불을 켜줌
  int DFS (int current, int before)

  • 만약 해당 노드가 리프 노드일 경우 결과 1리턴(불을 키지 않음)
  • 리프 노드가 아닐 경우
    - 자식 노드들 대상으로 DFS 진행
    - 자식 노드들의 리턴합이 0이라면 (해당 노드가 불을 킬 필요가 없다면) 1리턴(불을 켜지 않음)
    - 자식 노드들의 리턴합이 1이상이라면 (해당 노드가 불을 켜야함) 0리턴(불을 켜줌)

• 위처럼 루트부터 DFS를 진행하며 불을 켜야하는 노드들의 개수를 카운트 한다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int N, result = 0;
    public List<List<Integer>> map = new ArrayList<>();

    public int dfs(int cur, int before) {
        //리프 노드일 경우
        if (map.get(cur).size() == 1 && map.get(cur).get(0) == before)
            return 1;

        //리프 노드가 아닐 경우
        int tmpRes = 0;
        for (int i = 0; i < map.get(cur).size(); i++) {
            int next = map.get(cur).get(i);
            if (next == before) continue;
            tmpRes += dfs(next, cur);
        }

		//해당 노드가 불을 킬 필요 없음
		if (tmpRes == 0) 
        	return 1;
        
        //해당 노드가 불을 켜야함
        result++;
        return 0;
    }

    public int solution(int n, int[][] lighthouse) {
        //초기화
        N = n;
        for (int i = 0; i <= N; i++)
            map.add(new ArrayList<>());
        for (int i = 0; i < lighthouse.length; i++) {
            map.get(lighthouse[i][0]).add(lighthouse[i][1]);
            map.get(lighthouse[i][1]).add(lighthouse[i][0]);
        }

        //dfs로 켜야하는 등대 개수 판별
        dfs(1, 0);
        return result;
    }
}