99클럽 코테 스터디 4기 24일차 TIL - 프로그래머스: 전력망을 둘로 나누기(86971) Swift

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
프로그래머스	86971	전력망을 둘로 나누기	완전탐색	Lv.2	Swift

🚀 나의 접근 방법

아이디어는 간단하다. 직접 전선을 하나씩 끊어 보면서 두 전력망의 송전탑 개수의 차이를 구하면 된다. 즉, 완전탐색이다.

전선(간선)을 하나씩 제거하기 위해 wires 요소들을 순서대로 한 개씩 제거하고 (두 개의 전력망을 가진) 그래프로 만들었다. 그리고 그 그래프를 DFS를 통해 탐색하여 두 전력망의 송전탑 개수의 차이를 구했다.

이후 송전탑 개수의 차이 중에 최소를 반환하면 된다!

✍️ 나의 코드

Swift

import Foundation

func solution(_ n:Int, _ wires:[[Int]]) -> Int {    
    var result: [Int] = []
    for i in 0..<(n-1) {
        // 간선을 하나 제거하고 그래프를 만든다(전선 끊기)
        var graph: [[Int]] = Array(repeating: [], count: n+1)
        for (j, wire) in wires.enumerated() {
            if i == j { continue }
            graph[wire[0]].append(wire[1])
            graph[wire[1]].append(wire[0])
        }
        
        // DFS로 연결된 송전탐의 개수를 구한다
        var visited = Array(repeating: false, count: n+1)
        func dfs(_ v: Int, _ count: Int) -> Int {
            visited[v] = true
            var nCount = count+1
            for k in graph[v] {
                if !visited[k] {
                    nCount = dfs(k, nCount)
                }
            }
            return nCount
        }
        
        // 그래프를 탐색한다
        // 간선(전선)을 하나 끊었으므로 counts에는 2개가 추가 된다
        var counts: [Int] = []
        for t in 1...n {
            if !visited[t] {
                counts.append(dfs(t, 0))
            }
        }
        result.append(abs(counts[0]-counts[1]))
    }
    return result.min()!
}

🤔 회고

처음에는 복잡해 보여 당황했지만 막상 해보니 생각하는 데로 바로 풀렸다. 다만 코드가 길어지다 보니 인덱스 범위 실수가 잦았다. 더 집중해서 신속하게 풀어보자!