DFS, BFS | Graph Traversal(그래프 탐색) 문제 풀이 모음 | 2606번, 11725번, 2178번, 2667번, 14940번, 7576번,

DFS, BFS 문제부터 우선적으로 풀어야 될 것 같다.

출제 빈도가 높기 때문에 가장 먼저 감을 익혀야 하는 문제 유형 중 하나라고 생각하기 때문이다.

풀면서 틈틈이 구현(2) 문제도 풀 예정이다. 생각보다 짬이 안난다. 문제 하나 푸는데 시간이 꽤 오래 걸리기 때문이다....

차차 문제 푸는 속도가 빨라지지 않을까 싶다.

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

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

22.11.24 업데이트

22.11.26 업데이트

22.11.29 업데이트

22.11.30 업데이트

22.12.05 업데이트

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

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

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

백준 Swift PS. Contribute to SuminPark-developer/BaekJoonPS development by creating an account on GitHub.

github.com

그래프 탐색 문제 리스트

https://github.com/tony9402/baekjoon/tree/main/graph_traversal

백준 Swift 2606번

문제 유형 : 그래프 탐색(DFS)

난이도 : 실버3

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

var board: [[Int]] = Array(repeating: Array(repeating: 0, count: N + 1), count: N + 1)
var visited: [Bool] = Array(repeating: false, 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 count: Int = 0

func dfs(_ index: Int) { // 재귀
    for next in 1...N {
//        if next != index && board[index][next] == 1 && visited[next] == false { // 자기 자신 X, 인접하고, 미방문 시
        if board[index][next] == 1 && visited[next] == false { // 인접하고, 미방문 시
            visited[next] = true
            count += 1
            dfs(next)
        }
    }
}

visited[1] = true
dfs(1)
print(count)

백준 Swift 11725번

문제 유형 : 트리, DFS

난이도 : 실버2

[큐 풀이]

// MARK: - 11725번(참고 : https://t.ly/T01a)
class Dequeue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
}


let N = Int(readLine()!)!
var adj: [[Int]] = Array(repeating: [], count: N + 1) // 인접리스트

for _ in 0..<N-1 {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (a, b) = (input[0], input[1])
    
    adj[a].append(b)
    adj[b].append(a)
}

var parents = Array(repeating: -1, count: N + 1) // -1이면 미방문.
var myDeq: Dequeue<Int> = Dequeue([1])


while !myDeq.isEmpty {
    let index = myDeq.popFirst()
    
    for next in adj[index] {
        if parents[next] == -1 {
            parents[next] = index
            myDeq.pushLast(next)
        }
    }
}

for parent in parents[2...] {
    print(parent)
}

[DFS 풀이]

// MARK: - 11725번(DFS) // 참고 : https://t.ly/fvs-T
let N = Int(readLine()!)!
var adj: [[Int]] = Array(repeating: [], count: N + 1) // 인접행렬

for _ in 0..<N-1 {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (a, b) = (input[0], input[1])
    
    adj[a].append(b)
    adj[b].append(a)
}

var parents: [Int] = Array(repeating: -1, count: N + 1) // -1은 미방문.

func dfs(_ index: Int, _ p: Int) {
    parents[index] = p
//    print(parents)
    
    for next in adj[index] {
        if parents[next] == -1 {
            dfs(next, index)
        }
    }
}

dfs(1, 0)

for parent in parents[2...] {
    print(parent)
}

백준 Swift 2178번

문제 유형 : 최단거리 길찾기(BFS)

난이도 : 실버1

// MARK: - 2178번(BFS)
class Dequeue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
}

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var board: [[Int]] = Array(repeating: [], count: N + 1)
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: M + 1), count: N + 1)

for i in 1...N {
    board[i] = [0] + readLine()!.map{Int(String($0))!}
}

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]

func isValidCoord(_ y: Int, _ x: Int) -> Bool {
    return (1 <= y && y <= N) && (1 <= x && x <= M)
}

func bfs(_ startY: Int, _ startX: Int) -> Int {
    visited[startY][startX] = true // 시작점 방문
    let q = Dequeue([(startY, startX, 1)])
    
    while !q.isEmpty {
        let (y, x, d) = q.popFirst()
        
        if y == N && x == M { // 목적지에 도달 시,
            return d
        }
        
        for k in 0..<4 {
            let ny = y + dy[k]
            let nx = x + dx[k]
            let nd = d + 1
            if isValidCoord(ny, nx) && !visited[ny][nx] && board[ny][nx] == 1 { // 유효 범위이고, 미방문이고, 길이면,
                visited[ny][nx] = true
                q.pushLast((ny, nx, nd))
            }
            
        }
    }
    return -1 // 여기 올 일은 없음.
}

let answer = bfs(1, 1)
print(answer)

백준 Swift 2667번

문제 유형 : DFS / BFS

난이도 : 실버1

BFS 풀이

// MARK: - 2667번(BFS)
class Dequeue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
}
let N = Int(readLine()!)!
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: N), count: N)
var board: [[Int]] = []
for _ in 0..<N {
    let input = readLine()!.map{Int(String($0))!}
    board.append(input)
}

func isValidCoord(_ y: Int, _ x: Int) -> Bool {
    return (0 <= y && y < N) && (0 <= x && x < N)
}

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]

func bfs(_ startY: Int, _ startX: Int) -> Int {
    visited[startY][startX] = true
    let q = Dequeue([(startY, startX)])
    var count: Int = 1
    
    while !q.isEmpty {
        let (y, x) = q.popFirst()
        
        for k in 0..<4 {
            let ny = y + dy[k]
            let nx = x + dx[k]
            
            if isValidCoord(ny, nx) && !visited[ny][nx] && board[ny][nx] == 1 { // 유효범위고, 미방문상태고, 주택이 있으면, (유효범위부터 체크해야 index 에러 안생김.)
                visited[ny][nx] = true
                count += 1
                q.pushLast((ny, nx))
            }
        }
    }
    return count
}


var answers: [Int] = []
for y in 0..<N {
    for x in 0..<N {
        if board[y][x] == 1 && !visited[y][x] { // 집이 있고, 미방문이면,
            let answer = bfs(y, x)
            answers.append(answer)
        }
    }
}

answers.sort(by: <)
print(answers.count)
print(answers.map{String($0)}.joined(separator: "\n"))

DFS 풀이

// MARK: - 2667번(DFS)
let N = Int(readLine()!)!
var board: [[Int]] = []
board.append(Array(repeating: 0, count: N + 1))
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: N + 1), count: N + 1)

for _ in 0..<N {
    let input = readLine()!.map{Int(String($0))!}
    board.append([0] + input)
}

func isValidCoord(_ y: Int, _ x: Int) -> Bool {
    return (1 <= y && y <= N) && (1 <= x && x <= N)
}

var count: Int = 0
let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
func dfs(_ y: Int, _ x: Int) {
    visited[y][x] = true
    count += 1
    
    for k in 0..<4 {
        let ny = y + dy[k]
        let nx = x + dx[k]
        
        if isValidCoord(ny, nx) && board[ny][nx] == 1 && !visited[ny][nx] {
            dfs(ny, nx)
        }
        
    }
    
    
}


var answers: [Int] = []
for y in 1...N {
    for x in 1...N {
        if board[y][x] == 1 && !visited[y][x] {
            dfs(y, x)
            answers.append(count)
            count = 0
        }
    }
}

answers.sort(by: <)
print(answers.count)
for answer in answers {
    print(answer)
}

백준 Swift 12940번

문제 유형 : BFS

난이도 : 실버1

호기롭게 풀었는데 시간초과가 났다. 왜 그런지 고민해봐도 잘 모르겠어서 다른 풀이를 참고했다.

각 인덱스 -> 목표지점까지 BFS를 돌렸었는데, 그렇게 하면 시간초과가 난다.

반대로 목표지점 -> 각 인덱스로 BFS를 돌리면 된다!

// MARK: - 14940번(BFS / 참고 : https://www.acmicpc.net/source/49390198)
class Dequeue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
}

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

var board: [[Int]] = []
board.append(Array(repeating: 0, count: m + 1))

var goal: (y: Int, x: Int) = (0, 0)
for y in 1...n {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    board.append([0] + input)
    for (x, num) in input.enumerated() {
        if num == 2 {
            goal = (y, x + 1) // 목표위치 저장.
        }
    }
}

var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: m + 1), count: n + 1)

func isValidCoord(_ y: Int, _ x: Int) -> Bool {
    return (1 <= y && y <= n) && (1 <= x && x <= m)
}

var answers: [[Int]] = Array(repeating: Array(repeating: 0, count: m), count: n)

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
func bfs(_ startY: Int, _ startX: Int) {
    visited[startY][startX] = true
    let q = Dequeue([(startY, startX, 0)])
    
    while !q.isEmpty {
        let (y, x, count) = q.popFirst()
        answers[y-1][x-1] = count
        
        for k in 0..<4 {
            let ny = y + dy[k]
            let nx = x + dx[k]
            if isValidCoord(ny, nx) && (board[ny][nx] == 1 || board[ny][nx] == 2) && !visited[ny][nx] { // 유효 범위고, 갈 수 있는 땅이고, 미방문이면,
                visited[ny][nx] = true
                q.pushLast((ny, nx, count + 1))
            }
        }
    }
}

bfs(goal.y, goal.x) // goal을 기준으로 bfs를 돌림.

for y in 1...n {
    for x in 1...m {
        if !visited[y][x] && board[y][x] == 1 { // 원래 갈 수 있는 땅인데 도달할 수 없는 위치면,
            answers[y-1][x-1] = -1
        }
    }
}

for answer in answers {
    let temp = answer.map{String($0)}.joined(separator: " ")
    print(temp)
}

BFS 초기 풀이(시간초과)

// MARK: - 14940번(BFS)
class Dequeue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
}

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

var board: [[Int]] = []
board.append(Array(repeating: 0, count: m + 1))

for _ in 0..<n {
    board.append([0] + readLine()!.split(separator: " ").map{Int(String($0))!})
}

var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: m + 1), count: n + 1)

func isValidCoord(_ y: Int, _ x: Int) -> Bool {
    return (1 <= y && y <= n) && (1 <= x && x <= m)
}

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
func bfs(_ startY: Int, _ startX: Int) -> Int {
    visited[startY][startX] = true
    let q = Dequeue([(startY, startX, 0)])
    
    if board[startY][startX] == 0 { // 원래 갈 수 없는 땅인 위치면,
        return 0
    }
    
    while !q.isEmpty {
        let (y, x, count) = q.popFirst()
        
        if board[y][x] == 2 {
            return count
        }
        
        for k in 0..<4 {
            let ny = y + dy[k]
            let nx = x + dx[k]
            if isValidCoord(ny, nx) && (board[ny][nx] == 1 || board[ny][nx] == 2) && !visited[ny][nx] { // 유효 범위고, 갈 수 있는 땅이고, 미방문이면,
                visited[ny][nx] = true
                q.pushLast((ny, nx, count + 1))
            }
        }
    }
    return -1 // 원래 갈 수 있는 땅인데 도달할 수 없으면 -1
}

var answers: [[Int]] = Array(repeating: Array(repeating: 0, count: m), count: n)
for y in 1...n {
    for x in 1...m {
        if board[y][x] == 2 || board[y][x] == 0 { // bfs돌 필요 없음.
            answers[y-1][x-1] = 0 // 결과값 저장.
        }
        else {
            answers[y-1][x-1] = bfs(y, x) // 결과값 저장.
            visited = Array(repeating: Array(repeating: false, count: m + 1), count: n + 1) // 방문기록 초기화.
        }
    }
}

for answer in answers {
    let temp = answer.map{String($0)}.joined(separator: " ")
    print(temp)
}

백준 Swift 7576번

문제 유형 : BFS

난이도 : 골드5

// MARK: - 7576번(BFS)
class Dequeue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        enQueue = queue
    }
    
    func pushLast(_ element: T) {
        enQueue.append(element)
    }
    
    func pushFirst(_ element: T) {
        deQueue.append(element)
    }
    
    func popLast() -> T {
        if enQueue.isEmpty {
            enQueue = deQueue.reversed()
            deQueue.removeAll()
        }
        return enQueue.popLast()!
    }
    
    func popFirst() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
}

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (M, N) = (input[0], input[1])
var board: [[Int]] = []
var visited: [[Int]] = Array(repeating: Array(repeating: -1, count: M), count: N)

for _ in 1...N {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    board.append(input)
}

func isValidCoord(_ y: Int, _ x: Int) -> Bool {
    return (0 <= y && y < N) && (0 <= x && x < M)
}

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]
let q: Dequeue<(Int, Int)> = Dequeue([])

func bfs() {
    
    while !q.isEmpty {
        let (y, x) = q.popFirst()
        
        for k in 0..<4 {
            let ny = y + dy[k]
            let nx = x + dx[k]
            
            if isValidCoord(ny, nx) && board[ny][nx] == 0 && visited[ny][nx] == -1 { // 유효범위고, 토마토가 있고, 미방문상태면
                visited[ny][nx] = visited[y][x] + 1
                q.pushLast((ny, nx))
            }
        }
    }
}

for y in 0..<N {
    for x in 0..<M {
        if board[y][x] == 1 {
            visited[y][x] = 0
            q.pushLast((y, x))
        }
        else if board[y][x] == -1 { // 애초에 방문할 수 없는 곳이면,
            visited[y][x] = -2 // 미방문과 애초에 방문할 수 없는 곳 구분을 위해 -2로 저장. : 예제 input3.
        }
    }
}

bfs()

let visitedTemp = visited.flatMap{$0}
if visitedTemp.contains(-1) { // 미방문한 곳이 있다면,
    print(-1)
}
else { // 모두 방문했다면,
    print(visitedTemp.max()!) // 전부 익는데까지 걸리는 시간 = 최대값.
}

저작자표시 비영리 변경금지

DFS, BFS | Graph Traversal(그래프 탐색) 문제 풀이 모음 | 2606번, 11725번, 2178번, 2667번, 14940번, 7576번,

백준 Swift 2606번

백준 Swift 11725번

백준 Swift 2178번

백준 Swift 2667번

백준 Swift 12940번

백준 Swift 7576번

전체 방문자

공지사항

전체 카테고리

블로그 인기글

태그

티스토리툴바

백준 Swift 2606번

백준 Swift 11725번

백준 Swift 2178번

백준 Swift 2667번

백준 Swift 12940번

백준 Swift 7576번

전체 방문자

공지사항

전체 카테고리

블로그 인기글

최근 글

최근댓글

태그

티스토리툴바