[프로그래머스][Swift] 등대 - Level3

 

프로그래머스 문제 [ 링크 ]

 

간단한 문제 요약

n개의 등대가 있고, 등대와 등대 사이 오가는 뱃길은 n-1개 존재한다. 어느 등대에서 출발하든, 다른 모든 등대로 이동할 수 있다. 몇개의 등대만을 켜서 전력을 아끼려구 한다. 한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져있도록 등대를 켜 두어야 한다.

문제 풀이

처음엔 그리디하게 문제를 접근했는데 가장 많이 연결된 등대를 키지 않고도 그 주위의 등대들을 켜 두면, 최소한의 켜진 등대 개수가 구해질 수 있었습니다. (x)

 

"한 정점에서 다른 모든 등대로 이동할 수 있다 + n개의 등대 및 뱃길은 n-1개 존재한다." 에서 이 문제는 사이클이 없는 그래프임을 알 수 있습니다. (트리)(n개의 정점 중 간선이 n-1개)

 

 

dfs와 dp를 통해 특정 정점에서 등대를 켤 수 있도록 켜야 할 등대의 수를 최소화함으로 최적화를 해나갔습니다. dfs를 통해 sub tree를 탐색하며, 자식 노드들에 대한 등대 켜진 상태, 꺼진 상태를 고려해 부모 노드에서 등대 켜야하는지, 안 켜도 되는지 여부를 dp를 통해 "자식 노드들이 최소한 하나의 등대가 켜진 상태가 되도록" 하기 위해 필요한 최소 개수의 등대를 계산해나갑니다.

 

여기서 중요한 것은 dfs의 매개변수 node에 대해, 켜진상태 또는 꺼진 상태 둘 중 최소 개수를 구하기 위해서는, 서브 트리의 등대들의 최적해를 구해나가야 합니다. 이는 dfs를 통해서 탐색되며, 리프노드는 dp[리프노드]에 [0 or 1] 의 값을 갖게됩니다. dp[리프노드] 0번째 원소는 등대 꺼진 개수를 의미하고, 1번째 원소는 켜진 등대를 의미하고 더 나아가 dp[특정 노드]의 index 0은 꺼진 등대 개수, 1은 켜진 등대 개수를 의미합니다.

 

dp[node][0]은 node의 등대가 꺼진 경우입니다. 이때 이웃 등대는 반드시 켜져야 합니다.

(dp[node][0] += dp[neighbor][1] // 이웃이 반드시 켜진 경우)

 

dp[node][1]은 node의 등대가 켜진 경우입니다. 이웃 등대는 켜져도 되고 꺼져도 되는데 이때 어느 경우를 선정 할 지의 최적해는 해당 dp[이웃노드]의 켜진 등대 개수 최소값을 반영하면 됩니다.

dp[node][1] += min(dp[neighbor][0], dp[neighbor[1]) // 탐색중인 노드의 등대가 켜진 경우, 이웃 노드는 꺼져도되고, 켜져도 되는데 최소값 반영!!

 

시간복잡도: dfs 탐색활용하므로 O(n)

코드

func solution(_ n: Int, _ lighthouse: [[Int]]) -> Int {
  var graph = Array(repeating: [Int](), count: n+1)
  for nodes in lighthouse {
    graph[nodes[0]].append(nodes[1])
    graph[nodes[1]].append(nodes[0])
  }
  
  var dp = Array(repeating: [0,1], count: n+1)
  var visited = Array(repeating: false, count: n+1)
  
  func dfs(_ node: Int) {
    visited[node] = true
    for neighbor in graph[node] where !visited[neighbor] {
      dfs(neighbor)
      dp[node][0] += dp[neighbor][1]
      dp[node][1] += dp[neighbor].min()!
    }
  }
  
  dfs(1)
  return min(dp[1][0],dp[1][1])
}