'그래프 탐색' 문제 풀이(DFS, BFS) | 백준 Swift 2606번, 1260번

 

약간의 몸풀기 수학챕터를 어느정도 풀었고...

이제는 메인 문제 타입 중 하나인 DFS, BFS를 풀 차례다.

 

---

문제 풀이를 할 때 마다 계속 추가됩니다.

cmd + F 를 통해 문제번호 찾기를 추천드립니다.

 

 

25.02.12 업데이트

25.02.16 업데이트

 

아래 깃허브 주소에서 백준 Swift 문제풀이를 확인하실 수 있습니다.

https://github.com/SuminPark-developer/BaekJoonPS

GitHub - SuminPark-developer/BaekJoonPS: 백준 Swift PS

---

백준 Swift 2606번

문제 유형 : DFS

난이도 : 실버3

// MARK: - 2606번(DFS)
let M = Int(readLine()!)!
let N = Int(readLine()!)!

var board: [[Int]] = Array(repeating: Array(repeating: 0, count: M + 1), count: M + 1)
var visited = Array(repeating: false, count: M + 1)

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (y, x) = (input[0], input[1])
    
    board[y][x] = 1
    board[x][y] = 1
}

func dfs(_ index: Int) {
    
    for next in 1...M {
        if board[index][next] == 1 && visited[next] == false {
            visited[next] = true
            dfs(next)
        }
    }
}

dfs(1) // 1번컴퓨터 감염 시작
visited[1] = false // 1번컴퓨터는 제외
print(visited.filter{$0 == true}.count)

 

---

백준 Swift 1260번

문제 유형 : DFS, BFS

난이도 : 실버2

// MARK: - 1260번(DFS, BFS)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M, V) = (input[0], input[1], input[2])

var board: [[Int]] = Array(repeating: Array(repeating: 0, count: N + 1), count: N + 1)
var visited: [Bool] = Array(repeating: false, count: N + 1)
//var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: N + 1), count: N + 1)

for _ in 0..<M {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (y, x) = (input[0], input[1])
    board[y][x] = 1
    board[x][y] = 1
}

var answerDFS: [Int] = [V] // V는 무조건 첫방문

func dfs(_ index: Int) {
    visited[index] = true
    
    for next in 1...N {
        if board[index][next] == 1 && visited[next] == false { // 연결되어 있고, 미방문이면,
            visited[next] = true
            answerDFS.append(next)
            
            dfs(next)
        }
    }
}
dfs(V)

class Deque<T> {
    var enQue: [T]
    var deQue: [T] = []
    
    var count: Int {
        return enQue.count + deQue.count
    }
    
    var isEmpty: Bool {
        return enQue.isEmpty && deQue.isEmpty
    }
    
    init(_ que: [T]) {
        self.enQue = que
    }
    
    func pushFirst(_ element: T) {
        deQue.append(element)
    }
    
    func pushLast(_ element: T) {
        enQue.append(element)
    }
    
    func popFirst() -> T {
        if deQue.isEmpty {
            deQue = enQue.reversed()
            enQue.removeAll()
        }
        return deQue.popLast()!
    }
    
    func popLast() -> T {
        if enQue.isEmpty {
            enQue = deQue.reversed()
            deQue.removeAll()
        }
        return enQue.popLast()!
    }
}

visited = Array(repeating: false, count: N + 1)
var myDeque = Deque([V])
var answerBFS: [Int] = []

func BFS(_ index: Int) {
    visited[index] = true
    
    while !myDeque.isEmpty {
        let currentY = myDeque.popFirst()
        answerBFS.append(currentY)
        
        for next in 1...N {
            if board[currentY][next] == 1 && visited[next] == false {
                myDeque.pushLast(next)
                visited[next] = true
            }
        }
    }
}

BFS(V)
print(answerDFS.map{String($0)}.joined(separator: " "))
print(answerBFS.map{String($0)}.joined(separator: " "))

 

---