[백준/Swift] 1260번: DFS와 BFS

 

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

1260번: DFS와 BFS

 

전에 풀었던 문제였는데 음 Swift로는 처음 풀어본다.

c++과 유사한 풀이인데 입력받는 형식이 조금 달라져서 익히기 위해 문제를 다시 풀어봤다!

 

import Foundation

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let n = input[0]
let m = input[1]
let v = input[2]

var graph = [[Int]](repeating: [], count: n+1)
for _ in 0..<m {
    let vertices = readLine()!.split(separator: " ").map{ Int(String($0))! }
    graph[vertices[0]].append(vertices[1])
    graph[vertices[1]].append(vertices[0])
}

for i in 1...n {
    graph[i] = graph[i].sorted()
}

func BFS() { //while
    var queue = [v]
    var front = 0
    visited[v] = true
    
    while queue.count > front {
        let x = queue[front]
        print(x, terminator: " ")
        front += 1
        
        for next in graph[x] {
            guard !visited[next] else { continue }
            visited[next] = true
            queue.append(next)
        }
    }
}

func DFS(now: Int) { //recursion
    visited[now] = true
    print(now, terminator: " ")
    
    for next in graph[now] {
        guard !visited[next] else { continue }
        DFS(now: next)
    }
}

var visited = [Bool](repeating: false, count: n+1)
DFS(now: v)
print("")
visited = [Bool](repeating: false, count: n+1)
BFS()

 

BFS는 queue를 이용한 반복문으로 넓게 탐색하고

DFS는 재귀호출을 통해 한 정점에서 깊게 탐색한다.

visited로 중복 방문을 방지한다.