참고한 블로그

(Swift) 백준 1743 음식물 피하기

제가 만든 포스팅입니다ㅎㅎ 아래에서 사용하는 연결된 node 갯수를 세는 dfs에 대한 자세한 설명이 있습니다.

문제 풀이 아이디어

문제에서 시키는 대로 하면 됩니다. 주어진 wire를 완전탐색하면서 하나하나 끊어보고 dfs를 통해 두 전력망의 송전탑의 수를 세면 됩니다. 말은 쉬운데 구현은 좀 깁니다ㅎㅎ;;;

참고로 송전탑이 tree의 형태로 연결되어 있다고 했으므로 어느 wire를 끊던지 간에 2개의 전력망으로 나누어 집니다. (tree는 순환이 없기 때문입니다.)

그리고 한 node에서 다른 node로 가는 간선을 찾기 위해서 wire 배열을 그대로 사용하면 시간복잡도가 O(n)입니다. 인접 행렬로 바꾸어서 시간복잡도를 O(1)으로 줄입시다.

나머지는 코드를 보면서 설명을 드리겠습니다/

코드

import Foundation

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
    // 연결된 node의 갯수를 세는 dfs
    func dfs(_ now: Int) -> Int {
        visited[now] = true //👉 방문한 송전탑은 체크해두어야 함
        var count = 1
        
        for i in 1...n {
            if !visited[i] && matrix[now][i] {
                count += dfs(i)
            }
        }
        
        return count
    }
    
    // 간선을 연결 행렬로 표현하기
    var matrix = Array(repeating: Array(repeating: false, count: n + 1), count: n + 1)
    for wire in wires {
        let v1 = wire[0]
        let v2 = wire[1]
        matrix[v1][v2] = true
        matrix[v2][v1] = true
    }
    
    // 방문 체크 배열 및 최솟값을 저장할 변수
    var visited = Array(repeating: false, count: n + 1)
    var ans = Int.max

    // 연결된 모든 전선을 순회하면서 끊고 송전탑 세기
    for wire in wires {
        
        let v1 = wire[0]
        let v2 = wire[1]
        
        // 전선 끊기
        matrix[v1][v2] = false
        matrix[v2][v1] = false
        
        // 각각의 전력망의 송전탑 수를 저장할 배열
        var counts = [Int]()
        
        // 전력망의 송전탑의 수를 dfs로 세기
        for i in 1...n {
            if !visited[i] {
                counts.append(dfs(i))
            }
        }
        
        // 송전탑 차이의 최솟값 업데이트
        ans = min(abs(counts[0] - counts[1]), ans)
        
        // 방문 배열 및 끊은 원상복구
        visited =  Array(repeating: false, count: n + 1)
        matrix[v1][v2] = true
        matrix[v2][v1] = true
    }
    
    return ans
}