[Swift 알고리즘] 백준 BOJ - 1260 DFS와 BFS

안녕하세요. 개발 중인 정주입니다.

 

오늘은 백준 BOJ - 1260 DFS와 BFS 문제를 풀었습니다.

 

---

목차

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

1260번: DFS와 BFS

 

---

풀이

이번 문제는 DFS와 BFS 예제 문제입니다.

노드와 간선을 입력 받고 DFS, BFS 결과를 출력하면 되는데요.

입력으로 주어지는 간선은 양방향이고 정점은 번호가 작은 것을 먼저 방문합니다.

 

BFS

BFS는 Queue를 이용해 방문이 필요한 곳과 방문하면 되는 곳을 체크하면서 연결된 노드를 추가하면 됩니다.

Queue이기 때문에 앞에서부터 pop을 하면서 방문합니다.

 

DFS

DFS는 두 가지 방법이 있습니다. 재귀를 이용한 방법과 Stack을 이용한 방법인데요.

재귀를 이용한 방법은 방문할 곳이 없을 때까지 연결된 노드를 인자로 전달하며 재귀 호출합니다.

재귀를 이용할 때는 오름차순으로 정렬해야 합니다.

 

Stack을 이용한 이용한 방법은 BFS와 거의 동일한 코드인데요.

방문이 필요한 노드와 방문한 노드를 체크하며 연결된 노드를 Stack에 추가합니다.

모든 노드를 방문할 때까지 맨 뒤 요소를 pop하며 추가합니다.

Stack을 이용할 때는 내림차순으로 정렬해야 합니다.

 

---

전체 코드

//1260 DFS와 BFS
import Foundation

var dotCount = 0, lineCount = 0, startNum = 0
var graph: [Int:[Int]] = [:]
var visitedNode: [Int] = []
var needVisitNode: [Int] = []

func inputData() {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    dotCount = input[0]
    lineCount = input[1]
    startNum = input[2]
}

func createGraph() {
    for i in 1...dotCount {
        graph.updateValue([], forKey: i)
    }
    
    for _ in 0..<lineCount {
        let input = readLine()!.split(separator: " ").map { Int(String($0))! }
        
        graph[input[0]]?.append(input[1])
        graph[input[1]]?.append(input[0])
    }
}

func solution() {
    //1
//    for i in 1...dotCount {
//        graph[i]?.sort(by: >)
//    }
//    dfs()
    //2
    for i in 1...dotCount {
        graph[i]?.sort(by: <)
    }
    dfs2(node: startNum)
    print("")
    
    visitedNode = []
    needVisitNode = []
    
    for i in 1...dotCount {
        graph[i]?.sort(by: <)
    }
    bfs()
}

//반복문
func dfs() {
    needVisitNode.append(startNum)
    while !needVisitNode.isEmpty {
        let node = needVisitNode.removeLast()
        if visitedNode.contains(node) {
            continue
        }
        
        visitedNode.append(node)
        needVisitNode += graph[node] ?? []
    }
    
    print(visitedNode.map { String($0) }.joined(separator: " "))
}

//재귀
func dfs2(node: Int) {
    if visitedNode.contains(node) {
        return
    }
    visitedNode.append(node)
    print(node, terminator: " ")
    
    for i in graph[node]! {
        dfs2(node: i)
    }
}

func bfs() {
    needVisitNode.append(startNum)
    while !needVisitNode.isEmpty {
        let node = needVisitNode.removeFirst()
        if visitedNode.contains(node) {
            continue
        }
     
        visitedNode.append(node)
        needVisitNode += graph[node] ?? []
    }
    
    print(visitedNode.map { String($0) }.joined(separator: " "))
}

inputData()
createGraph()
solution()

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.