[백준] (Swift) 2636번 - 치즈 (BFS 풀이)

✅ 문제 링크

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

2636번: 치즈

 

✅ 문제 풀이 아이디어

문제가 굉장히 난해하게 생겼기 때문에 ,,,, 처음엔 BFS 문제인지 감이 안잡혔다. 인터넷을 찾아보니, 이 문제의 핵심은 다음과 같았다.

• 가운데 구멍뚫린 부분은 신경쓰지 않아도 된다. 어차피 BFS 로 탐색을 (0,0)부터 시작하게되면, 구멍으로 접근이 불가능하다. 외부 공기자리부터 탐색을 시작하면 어차피 구멍 내부로 접근할 수 없기떄문!! 
  • 가장자리는 항상 외부공기로 둘러쌓여있다. 그래서 (0,0)으로 시작하면, 항상 외부공기부터 탐색을 시작하게되고, 외부공기를 queue에 넣어 탐색을 하기 시작하니까 내부 공기로는 접근이 불가능하다는 결론이 나온다. (해석하기 힘들었음 ㅠㅠ )

그래서 (0,0)부터 항상 탐색을 시작하고, 치즈가 있는 자리 (1) 을 만나면 해당 자리를 0으로 바꿔주고, 방문처리르 해준다. (이 자리는 queue에 넣어주지 않는다.) 그리고 치즈를 녹였다면, cnt에 +1 해줌으로써 녹인치즈의 갯수를 세어줄것이다. 만약 마주친 자리가 계속해서 외부공기 (0)이라면, 방문처리를 해주고 queue에 넣는 방식을 반복한다.

녹인 치즈의 갯수는 cheeseCnt 배열에 넣어줄 것이다. 마지막에 '다녹기 전의 치즈의 수'를 출력해주어야하기 때문에, 배열로 각각의 단계마다 녹인 치즈의 갯수를 넣어주고, 맨 뒤에서 하나 앞에있는 값을 출력해줄 것이다.

그리고 녹인 시간 time 은 bfs가 한번돌아갈 때마다 +1을 해주어 출력해줄 것이다.

 

✅ 전체 소스코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/2636_%EC%B9%98%EC%A6%88/main.swift

GitHub - deslog/Algorithm

//
//  main.swift
//  Algorithm
//
//  Created by LeeJiSoo on 2022/07/06.
//
// ref: https://hooongs.tistory.com/264
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]
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

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) // bfs돌떄마다 0,0부터 시작하니까 visited 도 초기화
    var queue = [(Int, Int)]() // bfs돌 queue 초기화
    queue.append((0, 0))
    visited[0][0] = true
    cnt = 0  // 한번 돌 때 몇개의 치즈가 사라지는지 count -> 나중에 cheesecnt에 넣어줄거임
    
    while !queue.isEmpty {
        let xy = queue.removeFirst()
        let x = xy.0
        let y = xy.1
        
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx >= 0, nx < n, ny >= 0, ny < m, !visited[nx][ny] {
                if cheeseBoard[nx][ny] == 0 {  // 공기자리 일 때
                    visited[nx][ny] = true
                    queue.append((nx, ny))
                } else if cheeseBoard[nx][ny] == 1 { // 치즈가 있는 위치일 때
                    visited[nx][ny] = true
                    cheeseBoard[nx][ny] = 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])