[Swift 알고리즘] 백준 BOJ - 2636 치즈

Github

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

 

문제 링크

2636번: 치즈

 

풀이

이번 문제는 BFS 문제입니다.

가장자리의 치즈는 1시간이 지나면 녹습니다.

모든 치즈가 녹는데 소요되는 시간과 모두 녹기 직전 남은 치즈의 수를 출력해야 합니다.

 

while true {
    let meltingCount = meltingCheese()
    if meltingCount == 0 {
        break
    }
    
    cheeseCount = meltingCount
    time += 1
}

녹은 치즈가 존재할 동안 반복하고,

더이상 녹일 치즈가 없다면 모든 치즈가 녹은 것이므로 답을 출력합니다.

 

아래는 녹은 치즈의 수를 구하는 알고리즘입니다.

1. 치즈 바로 옆의 빈 공간을 찾습니다.

func findFirstCheese() -> (Int, Int)? {
    for i in 0..<h {
        for j in 0..<w {
            if map[i][j] == 1 {
                return (i, j-1)
            }
        }
    }
    
    return nil
}

map을 보면서 바로 옆에 치즈가 존재하는 공간을 구합니다.

가장자리에는 반드시 빈 공간이 와야 합니다.

즉 j == 0일 때 치즈가 올 수 없기 때문에 j-1을 구해도 문제가 없습니다.

 

2. Queue에 1에서 구한 좌표를 넣고 visited를 설정합니다.

var queue: [(h: Int, w: Int)] = [cheese]
var index = 0
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: w), count: h)
visited[cheese.0][cheese.1] = true

queue에 1에서 구한 좌표를 넣습니다.

시간복잡도를 위해 removeFirst( ) 대신 index 변수를 이용해 queue의 아이템을 가져옵니다.

 

visitied는 모두 false로 처리하고 1에서 구한 좌표는 true로 설정합니다.

visited를 미리 설정하는 이유는 반복 효율때문입니다.

 

3. 현재 좌표에서 상하좌우를 살핍니다.

let dh: [Int] = [-1, 1, 0, 0]
let dw: [Int] = [0, 0, -1, 1]

while index < queue.count {
    let node = queue[index]
    index += 1

    for i in 0..<4 { //상하좌우
        let nextH = node.h + dh[i]
        let nextW = node.w + dw[i]

        ...
    }
}

queue의 front 원소를 node로 설정하고 index를 1 증가시킵니다.

배열은 removeFirst( )를 하면 연산의 오버헤드가 발생하므로 위와 같은 기술을 사용합니다.

 

미리 선언해둔 dh, dw를 이용해 상하좌우를 살핍니다.

 

4. 치즈를 발견하면 녹이고, 빈 공간이면 queue에 추가합니다.

if map[nextH][nextW] == 1 { //치즈면 가장자리 치즈임
    map[nextH][nextW] = 0
    meltingCount += 1
} else if map[nextH][nextW] == 0 { //빈공간 탐색
    queue.append((nextH, nextW))
}

치즈를 발견하면 녹입니다.

빈 공간을 이동하며 찾은 치즈는 반드시 가장자리에 존재합니다.

 

만약 빈 공간이라면 queue에 append하여 탐색을 진행합니다.

 

전체 코드

import Foundation

let input = readLine()!.split { $0 == " " }.map { Int(String($0))! }
let w = input[1], h = input[0]

var map: [[Int]] = []
for _ in 0..<h {
    let input = readLine()!.split { $0 == " " }.map { Int(String($0))! }
    map.append(input)
}

let dh: [Int] = [-1, 1, 0, 0]
let dw: [Int] = [0, 0, -1, 1]

//다음 칸이 치즈인 빈칸 좌표 구하기
func findFirstCheese() -> (Int, Int)? {
    for i in 0..<h {
        for j in 0..<w {
            if map[i][j] == 1 {
                return (i, j-1)
            }
        }
    }
    
    return nil
}

func meltingCheese() -> Int {
    var meltingCount: Int = 0

    guard let cheese = findFirstCheese() else { return 0 }
    
    var queue: [(h: Int, w: Int)] = [cheese]
    var index = 0
    var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: w), count: h)
    visited[cheese.0][cheese.1] = true
    
    while index < queue.count {
        let node = queue[index]
        index += 1
        
        for i in 0..<4 { //상하좌우
            let nextH = node.h + dh[i]
            let nextW = node.w + dw[i]
            
            if nextH >= 0 && nextH < h && nextW >= 0 && nextW < w {
                if !visited[nextH][nextW] { //방문하지 않은 곳만 확인
                    visited[nextH][nextW] = true
                    
                    if map[nextH][nextW] == 1 { //치즈면 가장자리 치즈임
                        map[nextH][nextW] = 0
                        meltingCount += 1
                    } else if map[nextH][nextW] == 0 { //빈공간 탐색
                        queue.append((nextH, nextW))
                    }
                }
            }
        }
    }
    
    return meltingCount
}

var time: Int = 0
var cheeseCount: Int = 0
while true {
    let meltingCount = meltingCheese()
    if meltingCount == 0 {
        break
    }
    
    cheeseCount = meltingCount
    time += 1
}

print(time)
print(cheeseCount)

---

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

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

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