[Swift 알고리즘] 프로그래머스(Lv.2) - 전력망을 둘로 나누기

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.2) - 전력망을 둘로 나누기" 문제를 풀었습니다.

 

---

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 전력망을 둘로 나누기

 

---

풀이

이번 문제는 그래프 탐색 문제입니다.

주어진 트리의 엣지를 하나 끊었을 때 두 개 노드 그룹의 최소 개수 차이를 구하는 문제입니다.

이 문제의 최적화 방법의 핵심은 "트리"라는 점입니다.

 

1차 풀이

처음 제 생각대로 푼 풀이입니다.

그래프 탐색만을 중점으로 생각하고 트리의 특성을 살리지 못한 비효율적인 방법입니다.

 

문제의 엣지를 끊는다는 의미를 있는 그대로 받아들였고 매 반복마다 새로운 그래프를 생성했습니다.

하나의 엣지를 끊은 새로운 그래프로 bfs를 탐색한 것이죠.

 

만약 이 문제가 트리가 아니라 일반적인 그래프였다면 맞는 풀이였을 것입니다.

하지만 이 문제는 트리이기에 더 효율적인 방법이 존재했습니다.

 

2차 풀이

트리에서는 이미 방문을 했다고 표시를 하면 엣지를 끊은 것과 동일한 효과입니다. ㄴㅇOㅇㄱ

즉 매번 새로운 그래프를 만들 필요 없이 visited만 초기화 후 하나만 true로 바꿔 bfs를 돌리면 되는 것이죠.

이 방법으로 코드를 작성하니 코드도 짧아지고 시간도 훨씬 줄어들었습니다.

 

결과 비교

좌: 1차 풀이 / 우: 2차 풀이

왼쪽이 1차에 푼 결과이고 오른쪽이 2차에 푼 결과입니다.

4배 이상 빨라진 모습을 볼 수 있습니다.

 

자료구조의 특성을 제대로 파악해야 문제 최적화를 할 수 있다는 것을 배웠습니다.

 

---

전체 코드

import Foundation

func solution(_ n:Int, _ wires:[[Int]]) -> Int {    
    var graph: [Int: [Int]] = [:]
    for i in 1...n {
        graph.updateValue([], forKey: i)
    }

    for wire in wires {
        graph[wire[0]]?.append(wire[1])
        graph[wire[1]]?.append(wire[0])
    }

    func bfs(_ start: Int) -> Int {
        var queue: [Int] = [start]
        var index = 0

        while index < queue.count {
            let last = queue[index]
            index += 1

            visited[last] = true
            for node in graph[last]! {
                if !visited[node] {
                    queue.append(node)
                }
            }
        }

        return index
    }
    
    var visited = Array(repeating: false, count: n+1)
    visited[1] = true
    let count = bfs(2)
    var result = abs(count - (n - count))
    
    for i in 1...n {
        visited = Array(repeating: false, count: n+1)
        visited[i] = true
        let count = bfs(1)
        result = min(result, abs(count - (n - count)))
    }
    
    // print("counts: \(counts)")
    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.