BFS

BFS(Breadth First Search)

다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

 

구현방법

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌 때까지 2번을 반복
모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N).

 

예시코드

import Foundation

let board: [[Int]] = [
    [1,1,1,0,1,0,0,0,0,0],
    [1,0,0,0,1,0,0,0,0,0],
    [1,1,1,0,1,0,0,0,0,0],
    [1,1,0,0,1,0,0,0,0,0],
    [0,1,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0]
]
var vis = Array(repeating: Array(repeating: false, count: 502), count: 502)
let n = 7, m = 10
let dx = [1, 0, -1, 0]
let dy = [0, 1, 0, -1]

var queue = [(Int, Int)]()
vis[0][0] = true
queue.append((0, 0))
while !queue.isEmpty {
    let cur = queue.removeFirst()
    print("(\(cur.0), \(cur.1)) ", terminator: "")
    for dir in 0..<4 {
        let nx = cur.0 + dx[dir]
        let ny = cur.1 + dy[dir]
        if nx < 0 || nx >= n || ny < 0 || ny >= m {
            continue
        }
        if vis[nx][ny] || board[nx][ny] != 1 {
            continue
        }
        vis[nx][ny] = true
        queue.append((nx, ny))
    }
}
print("")

 

응용 1 - 거리 측정

다차원 배열에서 거리 측정을 통해 최단거리를 구하는 유형

출처 : 유튜브 BaaarkingDog

이런식으로 거리를 DFS로 적어서 최단경로를 구한다.

import Foundation

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

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

var board: [[String]] = []
for _ in 0..<n {
    let row = readLine()!.map { String($0) }
    board.append(row)
}

var dist: [[Int]] = Array(repeating: Array(repeating: -1, count: m), count: n)

var queue: [(Int, Int)] = []
queue.append((0, 0))
dist[0][0] = 0

while !queue.isEmpty {
    let cur = queue.removeFirst()
    
    for dir in 0..<4 {
        let nx = cur.0 + dx[dir]
        let ny = cur.1 + dy[dir]
        
        if nx < 0 || nx >= n || ny < 0 || ny >= m {
            continue
        }
        
        if dist[nx][ny] >= 0 || board[nx][ny] != "1" {
            continue
        }
        
        dist[nx][ny] = dist[cur.0][cur.1] + 1
        queue.append((nx, ny))
    }
}

print(dist[n-1][m-1] + 1)

 

응용2 - 시작점이 여러 개일 때

시작점이 여러개인 상황일 때는 모든 시작점을 큐에 넣고 BFS를 돌린다.

출처 : 유튜브 BaaarkingDog

예제 BOJ 7576 토마토

1. 모든 시작점을 이중 for문에 넣고 큐에 넣어둔다.

2. bfs를 돌리면서 마지막 index를 저장해둔다.

3. 0이 있는지 여부를 체크해서 만약 바뀌지 않은 토마토가 있다면 -1을 출력하게 한다.

import Foundation

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

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

var board: [[Int]] = []
var dist: [[Int]] = []
var queue: [(Int, Int)] = []

var idx = 0
var lastIdx = [0, 0]
var isCooked = true

for _ in 0..<n {
    let row = readLine()!.split(separator: " ").map { Int($0)! }
    board.append(row)
    dist.append(Array(repeating: -1, count: m))
}

for i in 0..<n {
    for j in 0..<m {
        if board[i][j] == 1 {
            queue.append((i, j))
        }
    }
}

while idx < queue.count {
    let cur = queue[idx]
    idx += 1
    
    for dir in 0..<4 {
        let nx = cur.0 + dx[dir]
        let ny = cur.1 + dy[dir]
        
        if nx<0 || nx>=n || ny<0 || ny>=m { continue }
        if board[nx][ny] == 0 {
            board[nx][ny] = 1
            queue.append((nx, ny))
            dist[nx][ny] = dist[cur.0][cur.1] + 1
            lastIdx = [nx, ny]
        }
    }
}

for i in 0..<n {
    for j in 0..<m {
        if board[i][j] == 0 {
            isCooked = false
        }
    }
}

if isCooked {
    print(dist[lastIdx[0]][lastIdx[1]]+1)
} else {
    print(-1)
}

 

응용3 - 시작점이 두 종류일 때

두가지 종류에 대해 모두 BFS를 돌려서 해결한다. q와 dist를 2개씩 만듬

BOJ 4179 불

1. 우선 지훈이는 신경쓰지말고 불에 대한 BFS를 돌려서 미리 각 칸에 불이 전파되는 시간을 구한다.

2. 지훈이에 대한 BFS를 돌리며 지훈이를 이동시킨다.

import Foundation

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

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

var board = [[String]]()
var dist1 = Array(repeating: Array(repeating: -1, count: m), count: n) // 불의 전파 시간
var dist2 = Array(repeating: Array(repeating: -1, count: m), count: n) // 지훈이의 이동 시간

for _ in 0..<n {
    let line = readLine()!.map { String($0) }
    board.append(line)
}

var q1 = [(Int, Int)]()
var q2 = [(Int, Int)]()

for i in 0..<n {
    for j in 0..<m {
        if board[i][j] == "F" {
            q1.append((i, j))
            dist1[i][j] = 0
        }
        if board[i][j] == "J" {
            q2.append((i, j))
            dist2[i][j] = 0
        }
    }
}

// 불에 대한 BFS
var q1Idx = 0
while q1Idx < q1.count {
    let cur = q1[q1Idx]
    q1Idx += 1
    for dir in 0..<4 {
        let nx = cur.0 + dx[dir]
        let ny = cur.1 + dy[dir]
        if nx < 0 || nx >= n || ny < 0 || ny >= m {
            continue
        }
        if dist1[nx][ny] >= 0 || board[nx][ny] == "#" {
            continue
        }
        dist1[nx][ny] = dist1[cur.0][cur.1] + 1
        q1.append((nx, ny))
    }
}

// 지훈이에 대한 BFS
var q2Idx = 0
while q2Idx < q2.count {
    let cur = q2[q2Idx]
    q2Idx += 1
    for dir in 0..<4 {
        let nx = cur.0 + dx[dir]
        let ny = cur.1 + dy[dir]
        if nx < 0 || nx >= n || ny < 0 || ny >= m {
            // 범위를 벗어났다는 것은 탈출에 성공했다는 의미. 큐에 거리 순으로 들어가므로 최초에 탈출한 시간을 출력하면 됨.
            print(dist2[cur.0][cur.1] + 1)
            exit(0)
        }
        if dist2[nx][ny] >= 0 || board[nx][ny] == "#" {
            continue
        }
        // 불이 지나간 시간이 지훈이가 지나갈 시간보다 작아야함
        if dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.0][cur.1] + 1 {
            continue
        }
        dist2[nx][ny] = dist2[cur.0][cur.1] + 1
        q2.append((nx, ny))
    }
}

print("IMPOSSIBLE") // 여기에 도달했다는 것은 탈출에 실패했음을 의미.

 

응용4 - 1차원에서의 BFS

2차원 배열에서 상하좌우로 방향을 두었듯이 문제 조건에 따라 BFS를 돌려서 해결한다.

BOJ 1697 숨바꼭질

 

1. 0~ 100002 사이의 dist배열을 -1을 넣어 생성한다.
2. dist[N]의 초기값을 0으로 넣어준다. (수빈이가 출발하는 시간 저장)
3. 동생을 찾은 시간이 넣어져서 -1이 없어질때까지 BFS를 돌린다.

 

import Foundation

let NK = readLine()!.split(separator: " ").map { Int($0)! }
let N = NK[0]
let K = NK[1]

var dist = Array(repeating: -1, count: 100002)

var idx = 0
var queue = [N]
dist[N] = 0
while dist[K] == -1 {
    let cur = queue[idx]
    idx += 1
    
    let nxtArr = [cur-1, cur+1, cur*2]
    for nxt in nxtArr {
        if nxt<0 || nxt > 100000 { continue }
        if dist[nxt] != -1 { continue }
        dist[nxt] = dist[cur] + 1
        queue.append(nxt)
    }
}

print(dist[K])