[프로그래머스Lv3/Python] 등대

등대
트리를 이용해 보는 문제이다.
풀이를 봐도 잘 이해가 가지 않아서 다시 정리해보려고 한다.

첫 문제접근

시간복잡도

• 2 ≤ n ≤ 100,000

이정도의 시간 복잡도에서는 이중반복문을 사용하면 안 된다는 생각이 들었다. 그래서 내가 생각한 풀이는 딕셔너리를 사용하여 연결을 나타냈다.

여기서 leaf 노드란 자식 노드가 없는 노드를 말한다.

💥 그러나.. 놓쳤던 점, 주의해야 할 점❗

내가 문제를 잘 못 이해했었다..
위처럼 하게 되면이게 성립되는데, 이 그림에서 배는 지나갈 수가 없다. 3과 4 그리고 6과 7이 끊어져 있는 상태이기 때문이다. 이 그림은 아래처럼 변해야 한다.이게 문제에서 말하는 것이었다. 최소, 하나 걸러 하나는 켜져 있어야 한다.

문제 풀이

1. 딕셔너리를 이용해 연결 정보를 넣어둔다.
2. DFS를 이용해서 현재 노드가 켜졌을 때와 꺼졌을 때 두 개의 값을 반환한다.

아래 주석으로 설명하겠다.

from collections import defaultdict
import sys
sys.setrecursionlimit(1000001)

visited = [False] * 1000001 
nodes = defaultdict(list) # 기본값이 빈 리스트인 딕셔너리

def dfs(now):
    visited[now] = True  # 현재 노드 방문처리
    if nodes[now]==[]: # 본인이 leaf(자식 노드가 없는 노드)라면
        return 1, 0 #본인이 켜졌을 때와 꺼졌을 때 두 개의 값 반환
    
    # leaf가 아니라면 (자식 노드가 하나 이상 있는 경우)
    on, off = 1, 0  # 시작 값을 켰을 때와 껐을 때, 두 개로 나눠서 출발
    
    for nd in nodes[now]: # 자식 노드를 둘러본다
        if not visited[nd]:
        # 자식 노드 nd를 켰을 때와 껐을 때의 최소 점등 등대 개수
          child_on, child_off = dfs(nd) 
          
          # 내가 켜졌다면 자식 노드들은 켜지든 꺼지든 상관 없음 
          		#-> 자식 노드가 켜진 경우와 꺼진 경우 중 최소값을 더함
          on += min(child_on, child_off)
          
          # 내가 꺼졌다면 자식 노드들은 무조건 켜져야 함 
          		#-> 자식 노드가 켜진 경우의 값을 더함
          off += child_on
          
    return on, off  # 현재 노드를 켰을 때와 껐을 때의 최소 점등 등대 개수를 반환

def solution(n, lighthouse):
    for a, b in lighthouse:
        #연결 정보 생성
        nodes[a].append(b)
        nodes[b].append(a)
        
    on, off = dfs(1)  # 1번 노드에서 DFS를 시작
    return min(on, off)  # 켰을 때와 껐을 때의 최소 점등 등대 개수 중 작은 값을 반환

알게 된 것

딕셔너리 초반에 항상 아래처럼 선언하고 get( )을 사용하여 빈 값의 키를 넣어주곤 했다.

    dict={}
    for a,b in lighthouse:
        if not dict.get(a):
            dict[a]=0
        if not dict.get(b):
            dict[b]=0
        dict[a]+=1
        dict[b]+=1

defaultdict(list)를 이용해서 바로 빈 리스트의 값을 넣어줄 수 있다는 것을 알게 되었다. 좀 더 깔끔한 코드 구현이 가능할 것 같다.