-
[programmers/Swift] 전력망을 둘로 나누기Archive/Questions 2022. 5. 21. 20:28728x90
programmers.co.kr - 코딩테스트연습 - Lv.2 - 위클리 챌린지 - 전력망을 둘로 나누기
Constraints :
- n은 2 이상 100 이하인 자연수입니다.
- wires는 길이가 n-1인 정수형 2차원 배열입니다.
- wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
- 1 ≤ v1 < v2 ≤ n 입니다.
- 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.
// // 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/
728x90'Archive > Questions' 카테고리의 다른 글
[programmers/Swift] 올바른 괄호 (0) 2022.05.23 [programmers/Swift] 교점에 별 만들기 (0) 2022.05.22 [programmers/Swift] 피로도 (0) 2022.05.20 [programmers/Swift] 다음 큰 숫자 (0) 2022.05.17 [programmers/Swift] 땅따먹기 (0) 2022.05.16