[스위프트][백준 - 치즈][💛 골드4] (BFS)

🧞‍♂️ 난이도

💛 골드4

🧞‍♂️ 문제

치즈

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

🧞‍♂️ 유형

BFS

🧞‍♂️ 풀이

이 문제는 조금 더 쉬운 버전도 있는데 치즈 중요한 로직은 비슷하다.

알고리즘

1. BFS로 공기(0) 에 대해서만 탐색을 한다.
   • 치즈 배열을 따로 만들어놓고, 공기가 치즈와 만날때마다 1을 더해준다.
2. 치즈 배열에 2 이상이 저장된 좌표들은 전부 0으로 만들어준다 (치즈를 녹인다)
3. 녹인 치즈가 있으면 정답에 1을 더하고 1부터 다시 한다.
4. 녹인 치즈가 없으면 알고리즘 끝

---

🧞‍♂️ 예외 케이스

(0, 0) 에 치즈가 하나 있을때는 따로 예외 처리를 해줘야되는줄 알았는데 처리 안해줘도 통과가 됐었다.

🧞‍♂️ 스위프트 풀이

import Foundation

func bfs(_ src_x: Int, _ src_y: Int, _ board: inout [[Int]]) -> Bool {
    let xLimit = board.count
    let yLimit = board[0].count
    let dx = [1, -1, 0, 0]
    let dy = [0, 0, 1, -1]
    var visited = Array(repeating: Array(repeating: false, count: yLimit), count: xLimit)
    var cheeseAirCount = Array(repeating: Array(repeating: 0, count: yLimit), count: xLimit)
    var q: [[Int]] = []
    
    visited[src_x][src_y] = true
    q.append([src_x, src_y]) // x, y
    
    var counter = 0
    while counter < q.count {
        let data = q[counter]
        let x = data[0]
        let y = data[1]
        
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx >= xLimit || nx < 0 || ny >= yLimit || ny < 0 || visited[nx][ny] {
                continue
            }
            
            // if cheeze and valid cheese
            if board[nx][ny] == 1 {
                cheeseAirCount[nx][ny] += 1
            } else {
                visited[nx][ny] = true
                q.append([nx, ny])
            }
        }
        counter += 1
    }
    var isMelted = false

    for x in 0..<xLimit {
        for y in 0..<yLimit {
            if cheeseAirCount[x][y] >= 2 {
                board[x][y] = 0
                isMelted = true
            }
        }
    }
    return isMelted
}

let NM = readLine()!.split(separator: " ").compactMap { Int($0) }
let N = NM[0]
let M = NM[1]

var board: [[Int]] = []
for _ in 0..<N {
    board.append(readLine()!.split(separator: " ").compactMap { Int($0) })
}

var time = 0
while true {
    if bfs(0, 0, &board) {
        time += 1
    } else {
        break
    }
}

print(time)

맨 위로 이동하기

leetcode 카테고리 내 다른 글 보러가기