Swift Data Structure And Algorithm/Graph Algorithm
κΉμ΄μ°μ νμκ³Ό λλΉμ°μ νμ
youngjaeLee1026
2022. 4. 15. 13:10
1. λ¬Έμ
2. μ μΆλ ₯
3. μ μΆλ ₯ μμ
4. λ¬Έμ μ€κ³
- μ λ¬Έμ μμλ μ‘°μ¬ν΄μΌ νλ λΆλΆμ΄ μμ μ λ ₯μλ μ€λ¦μ°¨μμΌλ‘ μ λ ₯μ΄ λμ§λ§ κ³μ μ€λ¦μ°¨μμΌλ‘ μ λ ₯ λλ€λ 보μ₯μ΄ μκΈ° λλ¬Έμ
- κ·Έλν νμ μ μ μΈμ 리μ€νΈλ₯Ό μ λ ¬ν΄μ£Όλ μμ μ΄ νμν¨.
5. μ 체 μ½λ
//MARK: - κΉμ΄μ°μ νμκ³Ό λλΉμ°μ νμ
//MARK: - Framework
import Foundation
//MARK: - Type
struct Graph {
//MARK: - Property
var edges: [Int]
//MARK: - Initializer
init() {
self.edges = []
}
}
//MARK: - Vairable
var graph: [Graph] = []
var visited: [Bool] = []
//MARK: - Function
func dfs(_ x: Int) -> Void {
visited[x] = true;
print("\(x) ", terminator: "")
for i in stride(from: 0, to: graph[x].edges.count, by: 1) {
let y: Int = graph[x].edges[i]
if !visited[y] {
visited[y] = true
dfs(y)
}
}
}
func bfs(_ start: Int) -> Void {
var queue: [Int] = []
queue.append(start)
visited[start] = true
while !queue.isEmpty {
let current: Int = queue.removeFirst()
print("\(current) ", terminator: "")
for i in stride(from: 0, to: graph[current].edges.count, by: 1) {
let next: Int = graph[current].edges[i]
if !visited[next] {
visited[next] = true
queue.append(next)
}
}
}
}
func solution() -> Void {
//MARK: - Input
guard let input: [String] = readLine()?.components(separatedBy: " ") else { return }
let N: Int = input.map { Int($0) }[0] ?? 0
let M: Int = input.map { Int($0) }[1] ?? 0
graph = Array(repeating: Graph(), count: N + 10)
visited = Array(repeating: false, count: N + 10)
for _ in 0..<M {
guard let data: [String] = readLine()?.components(separatedBy: " ") else { return }
let a: Int = data.map { Int($0) }[0] ?? 0
let b: Int = data.map { Int($0) }[1] ?? 0
graph[a].edges.append(b)
graph[b].edges.append(a)
}
//MARK: - Process & Output
for i in 0..<N {
graph[i].edges.sort { $0 < $1 }
}
dfs(0)
visited = Array(repeating: false, count: N + 10)
print()
bfs(0)
}
solution()
μ 체μ½λλ μ¬κΈ°μμ νμΈν μ μμ΅λλ€.