Swift Data Structure And Algorithm/Graph Algorithm

κΉŠμ΄μš°μ„ νƒμƒ‰κ³Ό λ„ˆλΉ„μš°μ„ νƒμƒ‰

youngjaeLee1026 2022. 4. 15. 13:10

1. 문제

스크란샷 2022-04-15 13 14 54

2. μž…μΆœλ ₯

스크란샷 2022-04-15 13 15 02

3. μž…μΆœλ ₯ μ˜ˆμ‹œ

스크란샷 2022-04-15 13 15 10

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()

 

μ „μ²΄μ½”λ“œλŠ” μ—¬κΈ°μ—μ„œ 확인할 수 μžˆμŠ΅λ‹ˆλ‹€.