Skip to content

[Algorithm] DFS와 BFSΒ #168

@hwangJi-dev

Description

@hwangJi-dev

πŸ’¬Β λ¬Έμ œ

https://www.acmicpc.net/problem/1260


πŸ’¬Β Idea

  • DFSλ₯Ό μˆ˜ν–‰ν•  λ•Œ λ²ˆν˜Έκ°€ μž‘μ€ λ…Έλ“œλ“€λΆ€ν„° μˆœνšŒν•˜κΈ° μœ„ν•΄μ„œ 순회 배열을 μ •λ ¬ν•œ λ’€ λ’€μ§‘μ–΄μ„œ μ €μž₯ν•΄μ€€λ‹€.
  • BFSλ₯Ό μˆ˜ν–‰ν•  λ•Œλ„ λ²ˆν˜Έκ°€ μž‘μ€ λ…Έλ“œλ“€λΆ€ν„° μˆœνšŒν•˜κΈ° μœ„ν•΄μ„œ 순회 배열을 μ •λ ¬ν•˜μ—¬ μ €μž₯ν•΄μ€€λ‹€.

πŸ’¬Β ν’€μ΄

func solution1260() {
    let info = readLine()!.split(separator: " ").map({ Int(String($0))! })
    var graph: [Int: [Int]] = [:]

    for _ in 0..<info[1] {
        let nodes = readLine()!.split(separator: " ").map({ Int(String($0))! })
        
        if graph[nodes[0]] == nil {
            graph[nodes[0]] = [nodes[1]]
        } else {
            graph[nodes[0]]?.append(nodes[1])
        }
        
        if graph[nodes[1]] == nil {
            graph[nodes[1]] = [nodes[0]]
        } else {
            graph[nodes[1]]?.append(nodes[0])
        }
    }

    func dfs(graph: [Int: [Int]], start: Int) -> [Int] {
        var needToVisitStack: [Int] = [start]
        var visitedQueue: [Int] = []
        
        while !needToVisitStack.isEmpty {
            let node = needToVisitStack.removeLast()
            
            if visitedQueue.contains(node) { continue }
            
            visitedQueue.append(node)
            if let nodes = graph[node]?.sorted().reversed() {
                needToVisitStack += nodes
            }
        }
        
        return visitedQueue
    }

    func bfs(graph: [Int: [Int]], start: Int) -> [Int] {
        var needToVisitQueue: [Int] = [start]
        var visitedQueue: [Int] = []
        
        while !needToVisitQueue.isEmpty {
            let node = needToVisitQueue.removeFirst()
            
            if visitedQueue.contains(node) { continue }
            
            visitedQueue.append(node)
            if let nodes = graph[node]?.sorted() {
                needToVisitQueue += nodes
            }
        }
        
        return visitedQueue
    }

    print(dfs(graph: graph, start: info[2]).map({ String($0) }).joined(separator: " "))
    print(bfs(graph: graph, start: info[2]).map({ String($0) }).joined(separator: " "))
}

μ†Œμš”μ‹œκ°„ : 30λΆ„

Metadata

Metadata

Assignees

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions