[Swift] 백준_치즈(2638)

문제

 

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

2638번: 치즈

 

 

풀이

 

이 문제에서 중요한 것은 외부 공기와 접촉해야한다는 것이다. 처음에 아무생각없이 닿는 공기가 두 개 이상이면 바로 없애도록 해서 틀렸었다.

 

가장자리에는 치즈를 두지 않으므로 이를 이용해서 바깥 공기를 구해주면된다. 

 

처음에 풀었던 방식은 우선 바깥공기를 전부 배열에 넣고, 다시 처음부터 BFS를 돌려 치즈를 구한 뒤에 공기랑 닿는 면이 바깥공기 배열에 들어가 있는지 확인해서 해결했었다. 해결은 했지만 시간이 너무 오래걸려서 맞힌 사람 목록에 뜨지도 않는 수준이었다.

 

그래서 치즈와 공기를 구분하지 않고 한 번에 해결하는 방향으로 바꿔보았다. (0,0) 부터 BFS를 돌리며 0인 경우엔 visited값을 -1에서 0으로만 바꿔주고, 1인 경우에는 계속해서 1씩 더해줘서 2가 넘는다면 마주한 공기가 2면이 넘는다는 얘기이므로 해당 점들을 전부 0으로 바꿔주었다.

반복문 마지막엔 result에 1을 더해주어 remove에 값이 들어오지 않는다면 치즈가 없다는 얘기이므로 break와 함께 결과를 출력해주도록 하였다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = input[0]; let m = input[1]
var cheese: [[Int]] = []
for _ in 0..<n {
    cheese.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
var result = 0
while true {
    var queue = [[0,0]]
    var visited = Array(repeating: Array(repeating: -1, count: m), count: n)
    visited[0][0] = 0
    var idx = 0
    var check = false
    while idx < queue.count {
        let current = queue[idx]
        idx += 1
        for i in 0..<dx.count {
            let newX = current[0] + dx[i]
            let newY = current[1] + dy[i]
            if newX < 0 || newY < 0 || newX >= n || newY >= m {
                continue
            }
            if visited[newX][newY] == -1 {
                if cheese[newX][newY] == 0 {
                    visited[newX][newY] = 0
                    queue.append([newX,newY])
                } else {
                    visited[newX][newY] = 1
                }
            } else {
                if cheese[newX][newY] == 1 {
                    visited[newX][newY] += 1
                }
            }
        }
    }
    for i in 0..<n {
        for j in 0..<m {
            if visited[i][j] >= 2 {
                cheese[i][j] = 0
                check = true
            }
        }
    }
    if !check {
        print(result)
        break
    }
    result += 1
}

 

 

_____________________________________________________________________________________________________

 

 

시간이 엄청 차이났다. 좀 더 효율적인 방법으로 생각이 잘 안된다. 머리가 좋지않음.