[Algorithm/Swift] BOJ(골드4) - 2573 빙산

안녕하세요 제인입니다 :)

PS 글은 오랜만인 것 같은데.. 오늘은 백준 문제 중 하나를 정리해보려고 합니다!

BFS 문제인데 한번 더 생각해야 될 부분이 있는 문제여서 정리해두면 좋을 것 같아서 처음으로 백준 문제를 가져와봤습니다.

바로 시작하겠습니다 !

문제 링크

2573번: 빙산

문제 풀이

간단하게 문제 요구 사항을 정리해보자면, 2차원 배열에 빙산의 각 부분별 높이 정보가 주어지는데, 인접한 칸이 0일 경우(그림에서 빈칸), 빙산이 일년마다 그 칸에 인접한 빈칸의 개수만큼 줄어듭니다. 구해야 하는 것은 주어진 그래프가 두 개 이상으로 분리되는 데까지 걸리는 최소 시간(년)이었습니다.

 

인접한 노드 중 0인 노드의 개수를 구해 해당 칸이 0이 될 때까지 계산하고, 그래프가 언제 두 개로 분리되는지 구하면 되는 문제이기 때문에 BFS로 풀면 되겠다는 아이디어가 바로 떠올랐는데요,

 

1. BFS로 인접한 0의 개수 탐색

2. 빙산 녹이기

3. 두 덩어리로 나뉘거나, 모든 빙산이 0이 되면 결과값 출력 후 종료

 

위와 같은 방법으로 구현을 해서 돌려봤는데.. 생각한 결과가 나오지 않더라구요..??

그래서 다른 풀이들을 찾아봤는데,, 제가 놓친 부분이 있었습니다..

(1, 1) 위치의 노드에 인접한 빈칸은 2개(노란색 부분)이므로, 1년이 지나면 0이 됩니다. (1, 2) 위치의 노드도 인접한 빈칸이 2개(파란색 부분) 1년이 지나면 -2가 되어 2가 되고, 또 1년이 지나면 또 -2가 되어 2년 후에 0이 되는 것이 맞겠죠??

 

하지만,, 제가 짠 로직에서는 바로 옆 노드인 (1, 1) 노드가 1년 후 0이 되기 때문에 2년째 되는 해에 (1, 2) 노드의 인접한 빈칸 개수가 3개로 계산이 되고 있었습니다.. 해가 갈수록 점점 0이 되는 칸의 개수가 늘어나기 때문에 다음 결과 값에 영향을 줄 수 있다는 생각을 하지 못해서 결과가 생각한 것과 다르게 나오는 문제가 생겼는데요, 그렇다면 초기 배열을 저장해두고 해당 배열과 비교해주는 방식으로 풀이를 하면 원하는 결과가 나올 것 같네요!

 

⭐️ 이 문제의 구현 포인트 ⭐️

❌ 그래프의 현 상태를 기준으로 빙산을 녹이면 안됨

⭕️ 빙산을 얼마나 녹여야 되는지 계산할 때, 초기 그래프를 기준으로 계산하기

Swift 풀이 코드

import Foundation

let directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
let input = readLine()!.split(separator: " ").map {Int($0)!}
let (n, m) = (input[0], input[1])
var arr: [[Int]] = [] // 빙산 높이 정보 담는 2차원 배열
var visited: [[Int]] = Array(repeating: Array(repeating: 0, count: m), count: n) // 방문 여부 체크 (몇번째 년도에 방문했는지)

// 주어진 빙산의 높이 정보 arr에 저장
for _ in 0..<n {
    let row = readLine()!.split(separator: " ").map {Int($0)!}
    arr.append(row)
}

var count = 1 // 덩어리 개수
var answer = 0 // 몇번째 해인지 저장

func bfs(_ graph: inout [[Int]], _ x: Int, _ y: Int) {
    var queue = [(x, y)]
    while !queue.isEmpty {
        let (currentX, currentY) = queue.removeFirst()
        for (dx, dy) in directions {
            let qx = dx + currentX
            let qy = dy + currentY
            // 인접 노드 범위 체크 & 방문 여부 체크
            if qx >= 0 && qx < n && qy >= 0 && qy < m && visited[qx][qy] < answer {
                if graph[qx][qy] > 0 { // 해당 칸이 빙산인 경우
                    visited[qx][qy] = answer // 방문 표시
                    queue.append((qx, qy)) // 큐에 추가
                } else { // 해당 칸이 바다인 경우
                    graph[currentX][currentY] -= 1 // 빙산 높이 감소시킴
                }
            }
        }
    }
}

while count == 1 { // 빙산이 하나의 덩어리로 이어져 있는 동안 반복
    count = 0 // count 0으로 초기화. bfs 수행되면(= 녹일 빙산이 있다면) 1이 됨 
    answer += 1
    for i in 0..<n {
        for j in 0..<m {
            // 이번 해에 방문하지 않는 빙산 찾기
            if arr[i][j] > 0 && visited[i][j] < answer {
                visited[i][j] = answer 
                count += 1 // bfs가 2번 이상 호출되면 덩어리가 2개 이상이라는 뜻
                bfs(&arr, i, j)
            }
        }
    }
    if count == 0 { // 녹일 빙산이 없는 경우(= 다 0이라는 뜻)
        answer = 1
        break
    }
}

print(answer - 1)