프로그래머스 [Lv. 3] 등대 {언어 : Python} [8, 9 런타임 에러 해결]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/133500?language=python3

프로그래머스

정답 코드

import sys
sys.setrecursionlimit(10**6)

def solution(n, lighthouse):    
    adjL = [[] for _ in range(n+1)]
    dp = [0 for _ in range(n+1)]
    visited = [0 for _ in range(n+1)]
    def dfs(current, parent):
        for node in adjL[current]:
            if node == parent:
                continue
            if visited[node]:
                continue
            visited[node] = 1
            dfs(node, current)
            if dp[node] == 0:
                dp[current] = 1
        return
    
    for start, to in lighthouse:
        adjL[start].append(to)
        adjL[to].append(start)
    
    dfs(1, 0)
    answer = sum(dp)
    return answer

풀이 방법

1. 1번 노드부터 깊이 우선 탐색으로 들어간다.
2. 가장 깊은 곳에서 반환되면 자식 노드를 등대가 비추고 있는지 확인한다.
3. dp[node] == 0이면 현재 노드에서 등대를 켜야 하므로 dp[curren] = 1
4. 마지막으로 dp의 합을 반환하면 끝!

느낀점

• 쉽게 풀었지만 깊이 에러가 생길줄은 몰랐다.
• 8, 9번에서 런타임 에러가 났다면 sys.setrecursionlimit으로 깊이를 늘려주자.