[programmers/Swift] 전력망을 둘로 나누기

programmers.co.kr - 코딩테스트연습 - Lv.2 - 위클리 챌린지 - 전력망을 둘로 나누기

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

Constraints :

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

 

Solution.swift :

//
//  Created by Yongwoo Marco on 2022/05/19.
//  Copyright © 2022 Yongwoo Marco Kim. All rights reserved.
//

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
    var graph = [Int: [Int]](), results = [Int]()
    
    wires.forEach {
        for (i, j) in [($0[0], $0[1]), ($0[1], $0[0])] {
            if let vertexes = graph[i], !vertexes.contains(j) {
                graph[i]?.append(j)
            } else {
                graph.updateValue([j], forKey: i)
            }
        }
    }
        
    for cut in wires {
        let lhs = Set(bfs(start: cut[0], graph: graph, except: cut[1]))
        let rhs = Set(bfs(start: cut[1], graph: graph, except: cut[0]))
        
        if lhs.isDisjoint(with: rhs) {
            results.append(abs(lhs.count - rhs.count))
        }
    }
    
    return results.min() ?? 0
}

func bfs(start: Int, graph: [Int: [Int]], except: Int) -> [Int] {
    var lefts = graph, visited = [Int](), nexts = [start]
    
    lefts.removeValue(forKey: except)
    
    while let now = nexts.popLast() {
        if now == except { continue }
        visited.append(now)
        nexts.append(contentsOf: lefts[now] ?? [])
        lefts.removeValue(forKey: now)
    }

    return visited
}

print(solution(9, [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]])) // 3
print(solution(4, [[1,2],[2,3],[3,4]])) // 0
print(solution(7, [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]])) // 1

How I tried this :
DFS나 BFS 같은건 잘 떠오르지 않았지만 일단 문제를 들여다보았다.

내 아이디어는 간선을 모두 주어질때 그 간선이 끊어졌다 가정하고,

한쪽의 전력망, 다른 한쪽의 전력망을 구해서 비교하는 형태였다.

 

일단 Graph를 딕셔너리를 이용해서 구했다.

그리고 주어진 wires를 하나씩 방문하며 해당 wire가 끊어졌다고 가정하고

lhs, rhs 두 방면으로 다시 그래프를 이어서 해당 그래프에 정점 수 차를 구했다.

 

각 자 그래프를 다시 그릴때 서로의 점은 제외하는데, 연결된 경우가 있을 수 있어서 

두 그래프에 겹치는 정점이 있는지 확인 후 없는 경우만 정점 수 차를 저장했다.

 

가장 비슷한 수가 나온다는건 두 정점 수를 빼서 가장 작은 수 라는 말이기 때문에 min() 값을 넣었다.

 

 

What I got is :
BFS DFS 복습 필요

 

문제에 관한 모든 저작권 : https://programmers.co.kr/