[Swift] 백준 - DFS와 BFS

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

 

 

Swift로 DFS BFS 는 처음 풀어본다.

 

한번 기본적인 준비물을 알아보자.

 

DFS

1. 인접리스트
2. 시작 정점
3. 방문 배열

 

BFS

1. 인접리스트
2. 시작 정점
3. 방문 배열
4. 큐

 

DFS의 경우 방문 정점에 속한 하나의 정점의 또 다른 간선들을 다 확인하고 다음 간선을 확인하고

BFS의 경우 방문 정점에 속한 모든 정점을 확인하고 연결된 다음 간선으로 이동한다.

 

DFS 코드

import Foundation

func main() {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    let (N, M, V) = (input[0], input[1], input[2])

    // 인접 리스트를 담은 그래프
    var graph = [[Int]](repeating: [], count: N+1)

    for _ in 0..<M {
        let edge = readLine()!.split(separator: " ").map { Int($0)! }
        let (u, v) = (edge[0], edge[1])
        graph[u].append(v)
        graph[v].append(u)
    }

    // 오름차순 정렬
    for i in 0...N {
        graph[i].sort()
    }

    var visited = [Bool](repeating: false, count: N+1)

    // DFS 함수 정의
    func dfs(start: Int, nodes: [[Int]], visited: inout [Bool]) {
        if visited[start] { return }  // 이미 방문한 노드인 경우 리턴
        visited[start] = true
        print(start, terminator: " ")

        for nextNode in nodes[start] {
            dfs(start: nextNode, nodes: nodes, visited: &visited)
        }
    }

    // DFS 실행
    dfs(start: V, nodes: graph, visited: &visited)
}

// main 함수 실행
//main()

 

 

BFS 코드

import Foundation

func main() {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    let (N, M, V) = (input[0], input[1], input[2])

    // 인접 리스트를 담은 그래프
    var graph = [[Int]](repeating: [], count: N+1)

    for _ in 0..<M {
        let edge = readLine()!.split(separator: " ").map { Int($0)! }
        let (u, v) = (edge[0], edge[1])
        graph[u].append(v)
        graph[v].append(u)
    }

    // 오름차순 정렬
    for i in 0...N {
        graph[i].sort()
    }

    var visited = [Bool](repeating: false, count: N+1)

    // DFS 함수 정의
    func bfs(start: Int, nodes: [[Int]], visited: inout [Bool]) {
        
        var queue = [Int]()
        queue.append(start)
        
        while !queue.isEmpty{
            let node = queue.removeFirst()
            if !visited[node] {
                print(node, terminator: " ")
                visited[node] = true
                for nextNode in nodes[node]{
                    queue.append(nextNode)
                }
            }
        }
        
    }
    
    bfs(start: V, nodes: graph, visited: &visited)
       
}

// main 함수 실행
main()

 

즐 겁 다