[프로그래머스/Lv.3] - 등대

ZenTechie·2023년 5월 15일

PS

목록 보기

15/53

설명을 매우 잘해주신 분이 있어서 참고했습니다.

문제

인천 앞바다에는 1부터 n까지 서로 다른 번호가 매겨진 등대 n개가 존재합니다. 등대와 등대 사이를 오가는 뱃길이 n-1개 존재하여, 어느 등대에서 출발해도 다른 모든 등대까지 이동할 수 있습니다. 등대 관리자 윤성이는 전력을 아끼기 위하여, 이 중 몇 개의 등대만 켜 두려고 합니다. 하지만 등대를 아무렇게나 꺼버리면, 뱃길을 오가는 배들이 위험할 수 있습니다. 한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있도록 등대를 켜 두어야 합니다.

예를 들어, 아래 그림과 같이 등대 8개와 7개의 뱃길들이 있다고 합시다. 이 경우 1번 등대와 5번 등대 두 개만 켜 두어도 모든 뱃길은 양쪽 끝 등대 중 하나가 켜져 있으므로, 배들은 안전하게 운항할 수 있습니다.

등대의 개수 n과 각 뱃길이 연결된 등대의 번호를 담은 이차원 배열 lighthouse가 매개변수로 주어집니다. 윤성이가 켜 두어야 하는 등대 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

2 ≤ n ≤ 100,000
lighthouse의 길이 = n – 1
- lighthouse 배열의 각 행 [a, b]는 a번 등대와 b번 등대가 뱃길로 연결되어 있다는 의미입니다.
  - 1 ≤ a ≠ b ≤ n
  - 모든 등대는 서로 다른 등대로 이동할 수 있는 뱃길이 존재하도록 입력이 주어집니다.

입출력 예

n	lighthouse	result
8	[[1, 2], [1, 3], [1, 4], [1, 5], [5, 6], [5, 7], [5, 8]]	2
10	[[4, 1], [5, 1], [5, 6], [7, 6], [1, 2], [1, 3], [6, 8], [2, 9], [9, 10]]	3

입출력 예 설명

입출력 예 #1

본문에서 설명한 예시입니다.

입출력 예 #2

뱃길은 아래 그림과 같이 연결되어 있습니다. 윤성이가 이중 1, 6, 9번 등대 3개만 켜 두어도 모든 뱃길은 양쪽 끝 등대 중 하나가 켜져 있게 되고, 이때의 등대 개수 3개가 최소가 됩니다.

아이디어

모든 등대는 서로 다른 등대로 이동할 수 있는 뱃길이 반드시 존재한다.
한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있도록 등대를 켜 두어야 한다.

일단 근본적으로 생각해봐야 할 것은, 켜두어야 하는 등대의 최솟값을 구해야 한다는 것이다. 이것을 이분법적으로 생각해보면 등대를 최소로 켜둔 상황에서 특정 등대는 켜지거나 꺼지거나 둘 중 하나이다.

이를 분할하면, 특정 노드를 포함한 서브트리에서 특정 노드가 켜졌을 때(on) 최소로 켜진 등대 개수와 꺼졌을 때(off) 최소로 켜진 등대 개수중 최소를 답으로 가지면 된다. 이 과정을 루트노드에 대해서 수행하면 된다.

특정 노드가 on일 때, 특정 노드를 포함하는 서브트리에서 켜야하는 최소 등대 개수
특정 노드가 켜져있다면 이와 연결된 자식 노드들은 켜지던 꺼지던 상관이 없다. 그러므로 자식노드(c)로 dfs를 수행한 결과(dfs(c))인 c_on, c_off 중 최솟값을 골라서 합친다.

특정 노드가 off일 때, 특정 노드를 포함하는 서브트리에서 켜야하는 최소 등대 개수
특정 노드가 꺼져있다면 이와 연결된 자식 노드들은 무조건 켜져있어야 한다.
그러므로, 자식 노드(c)로 dfs를 수행한 결과(dfs(c))인 c_on을 합친다.

따라서, 위의 모든 과정을 루트노드에 대해서 DFS를 재귀적으로 수행하면, 최소로 켜야하는 등대의 개수를 얻을 수 있다.

이때, 루트 노드는 어떻게 정하는지도 생각해봐야 한다.
분명 문제에서 모든 등대는 서로 다른 등대로 이동할 수 있는 뱃길이 반드시 존재한다고 되어있다.

이 말을 풀어보면 모든 등대는 서로 연결되어 있으니 어떤 노드를 루트 노드로 선택해도 상관없다는 말이다.

알고리즘

어떤 노드를 루트노드로 선택해도 상관 없다 → 등대 연결 정보는 양방향이다.
특정 노드에서 연결된 모든 자식 노드를 확인해야 한다 → DFS

따라서, 양방향 그래프를 하나 만들고 이를 토대로 DFS를 수행한다.

코드

import sys
sys.setrecursionlimit(10 ** 6)

def solution(n, lighthouse):
    graph = [[] for _ in range(n + 1)] # 양방향 그래프
    check = [0] * (n + 1) # 방문 처리
    
    # 양방향 그래프 만들기
    for a, b in lighthouse:
        graph[a].append(b)
        graph[b].append(a)
    
    # DFS
    def dfs(x):
        check[x] = 1 # 방문처리
        
        # 리프 노드라면
        if not graph[x]:
            return 1, 0 # on, off
        
        # 리프 노드가 아니라면
        # 방문하지 않은 자식 노드를 리스트로 만든다.
        child = [nxt for nxt in graph[x] if not check[nxt]]
        
        # 점등, 소등
        on, off = 1, 0
        
        # 자식노드를 탐색하면서
        for c in child:
            c_on, c_off = dfs(c) # 해당 자식노드를 켜거나 끌 경우
            on += min(c_on, c_off) # 나(특정 노드)를 켤 경우
            off += c_on # 나(특정 노드)를 끌 경우 자식은 반드시 켜야한다.
        
        return on, off
    
    # 뱃길은 모두 이어져있으므로 시작 노드는 상관이 없다.
    on, off = dfs(1)
    
    return min(on, off) # 최소로 켜는 등대 개수를 반환한다.

설명

먼저 알고리즘의 과정은 다음과 같다.

루트 노드를 설정하고 dfs를 수행한다. → dfs(x)
방문처리를 한다. → check[x] = 1
2.1 리프 노드가 아니라면 방문하지 않은 자식 노드를 리스트로 만든다.
2.2 리프 노드라면 킬 경우와 끌 경우를 반환한다. → return 1, 0
만든 리스트안의 자식 노드를 탐색하면서, 해당 자식 노드로 위의 과정을 반복한다.(재귀호출) → dfs(c)
재귀호출이 종료되면, 루트 노드를 켤 경우에, 자식 노드를 켤 경우와 끌 경우 중 최솟값을 더한다. (루트 노드가 켜져있으면 자식 노드는 뭘 해도 상관없다.)
→ on += min(c_on, c_off)
루트 노드를 끌 경우에는 자식 노드가 반드시 켜져있어야 하므로, 자식 노드를 켤 경우를 더한다. → off += c_on
최종적으로 루트 노드를 킬 경우와 끌 경우를 반환한다. → return on, off