백준 - 치즈(Swift)

백준 - 치즈(Swift)

 

 

 문제 설명

 

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

2636번: 치즈

 

 나의 풀이

 

스스로의 기본기가 매우매우 부족하다고 느낀 문제였다.

 

문제를 푸는데 상당히 오랜시간이 걸렸는데 그 이유는 다음과 같다.

 

1. 모든 공기중에 노출된 치즈가 아닌 외부공기에 노출된 치즈만이 녹는다는 사실

2. 외부 공기와 내부공기를 어떻게 나눌지

3. 외부공기에 의해 녹은 치즈 이후에 생긴 공기에 대한 처리.

 

무엇보다 제일 큰 이유는 문제를 우습게 생각했기 때문인 것 같다.

보자마자 그냥 완전탐색으로 외부만 체크해서 녹이면 되겠다고 생각했는데 생각보다 고려할 게 많았던 것이다.

 

특히 3번이 조금 성가셨는데 이는 BFS를 돌릴때마다 visited를 초기화시킴으로써 처리를 할 수 있었다.

 

그리고 나는 외부치즈로 결정이 되면 새로운 숫자로 바꿔서 차별점을 주거나 치즈가 없는 경우 flag를 처리하지 않는 등의 좀 더 헷갈릴만한 것들을 추가하려했는데, 이보다는 방문표시여부는 강력한 배열이기 때문에 이를 이용해 처리하거나 flag는 함수의 리턴값에 대해서 처리함으로써 간결하게 표현하는 역량이 필요했다.

 

import Foundation

struct Point {
    let x: Int
    let y: Int
    
    init(_ x: Int, _ y: Int) {
        self.x = x
        self.y = y
    }
    
    var nexts: [Point] {
        return [
            Point(x+1, y),
            Point(x-1, y),
            Point(x, y-1),
            Point(x, y+1)
        ]
    }
}

let input = readLine()!.components(separatedBy:" ").map{Int($0)!}
let row = input[0], col = input[1]
var map = [[Int]]()
var tempMap = [[Int]]()
var visited = [[Bool]](repeating: [Bool](repeating: false, count: col), count: row)
let rowRange = 0...row-1
let colRange = 0...col-1
var result = 0
var cheezeCnt: [Int] = []

for _ in 0..<row {
    map.append(readLine()!.components(separatedBy:" ").map{Int($0)!})
}

var flag = false
while true {
    visited = [[Bool]](repeating: [Bool](repeating: false, count: col), count: row)
    tempMap = map
    BFS(0, 0)
    
    result += 1
    findOuterCheeze()
    
    // 바깥치즈가 존재하지않는다면 = 치즈가 다 떨어졌다면
    if !flag {
        break
    } else {
        meltingCheeze()
        map = tempMap
        flag = false
    }
}

print(result-1)
print(cheezeCnt[cheezeCnt.count-1])

// 처음 바깥벽들을 2로 지정
func BFS(_ x: Int, _ y: Int) {
    visited[x][y] = true
    var queue: [Point] = [Point(x, y)]
    
    while !queue.isEmpty {
        let curr = queue.removeFirst()
        for next in curr.nexts where rowRange ~= next.x && colRange ~= next.y {
            if !visited[next.x][next.y], tempMap[next.x][next.y] == 0 {
                visited[next.x][next.y] = true
                queue.append(next)
            } 
        }
    }
    
}

// 바깥 치즈들을 찾는 함수
func findOuterCheeze() {
    for i in 0..<row-1 {
        for j in 0..<col-1 {
            let p = Point(i, j)
            for next in p.nexts {
                if tempMap[i][j] == 1, tempMap[next.x][next.y] == 0, visited[next.x][next.y] {
                    visited[i][j] = true
                    flag = true
                    break
                }
            }
        }
    }
}

// 치즈를 녹이는 함수
func meltingCheeze() {
    var cnt = 0
    for i in 0..<row-1 {
        for j in 0..<col-1 {
            if tempMap[i][j] == 1, visited[i][j] {
                tempMap[i][j] = 0
                cnt += 1
            }
        }
    }
    cheezeCnt.append(cnt)
}

 

 

 다른 사람의 풀이

 

이분의 풀이는 나의 풀이보다 훨씬 깔끔했다.

외부의 공기를 true로 표현을 할 때 치즈인 부분은 큐에 안넣고 0으로만 바꿈으로써(방문표시도) 치즈였던 곳이 공기로 변할때의 로직을 쉽게 처리할 수 있었다.

그리고 bfs를 호출할때마다 visited를 초기화시킨다는 점과 tempArr을 만들지않고 cnt를 리턴함으로써 종료시점을 만드는 것도 좋은방법이였다.

 

import Foundation
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
var cheeseCnt = [Int]()
var cheeseBoard = [[Int]]()
var time = 0
var cnt = 0
let rowRange = 0...n-1
let colRange = 0...m-1

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

func bfs() -> Int {
    var visited = Array(repeating: Array(repeating: false, count: m), count: n)
    var queue = [(Int, Int)]()
    queue.append((0, 0))
    visited[0][0] = true
    cnt = 0
    
    while !queue.isEmpty {
        let p = queue.removeFirst()
        let curX = p.0
        let curY = p.1
        
        for next in [(curX+1, curY), (curX-1, curY), (curX, curY-1), (curX, curY+1)] {
            if rowRange ~= next.0, colRange ~= next.1, !visited[next.0][next.1] {
                if cheeseBoard[next.0][next.1] == 0 {
                    visited[next.0][next.1] = true
                    queue.append((next.0, next.1))
                } else if cheeseBoard[next.0][next.1] == 1 {
                    visited[next.0][next.1] = true
                    cheeseBoard[next.0][next.1] = 0
                    cnt += 1
                }
            }
        }
    }
    cheeseCnt.append(cnt)
    return cnt
}

while true {
    time += 1
    cnt = bfs()
    if cnt == 0 {
        break
    }
}

print(time-1)
print(cheeseCnt[cheeseCnt.count-2])