-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.swift
86 lines (81 loc) · 2.61 KB
/
main.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//
// main.swift
// SwiftAlgorithm
//
// Created by Lee Myeonghwan on 2023/01/16.
//
import Foundation
// BFS
func solution(_ n:Int, _ wires:[[Int]]) -> Int {
var minDiff = 100
func BFS(towerGraph: [[Bool]]) {
var visited = Array(repeating: false, count: n + 1)
var stack: [Int] = []
stack.append(1)
visited[1] = true
while !stack.isEmpty {
let checkPoint = stack.removeLast()
for i in 1...n {
if !visited[i] && towerGraph[checkPoint][i] {
visited[i] = true
stack.append(i)
}
}
}
let firstTowers = visited.filter{ $0 == true }.count
let secondTowers = n - firstTowers
let diff = abs(firstTowers - secondTowers)
if diff < minDiff {
minDiff = diff
}
}
for i in 0..<wires.count {
var cWires = wires
cWires.remove(at: i)
let towerGraphLine = Array(repeating: false, count: n + 1)
var towerGraph: [[Bool]] = Array(repeating: towerGraphLine, count: n + 1)
for wire in cWires {
let startPoint = wire[0]
let endPoint = wire[1]
towerGraph[startPoint][endPoint] = true
towerGraph[endPoint][startPoint] = true
}
BFS(towerGraph: towerGraph)
}
return minDiff
}
/* DFS
func solution(_ n:Int, _ wires:[[Int]]) -> Int {
var minDiff = 100
func DFS(towerGraph: [[Bool]], lineIndex: Int, visited: inout [Bool], towerCount: inout Int) {
for i in 1...n {
if !visited[i] && towerGraph[lineIndex][i] {
visited[i] = true
towerCount += 1
DFS(towerGraph: towerGraph, lineIndex: i, visited: &visited, towerCount: &towerCount)
}
}
}
for i in 0..<wires.count {
var cWires = wires
cWires.remove(at: i)
let towerGraphLine = Array(repeating: false, count: n + 1)
var towerGraph: [[Bool]] = Array(repeating: towerGraphLine, count: n + 1)
for wire in cWires {
let startPoint = wire[0]
let endPoint = wire[1]
towerGraph[startPoint][endPoint] = true
towerGraph[endPoint][startPoint] = true
}
var visited = Array(repeating: false, count: n + 1)
var towerCount = 0
DFS(towerGraph: towerGraph, lineIndex: 1, visited: &visited, towerCount: &towerCount)
let secondTowers = n - towerCount
let diff = abs(towerCount - secondTowers)
if diff < minDiff {
minDiff = diff
}
}
return minDiff
}
*/