티스토리 뷰

PS

[Swift] 백준_빙산(2573)

희철 2023. 1. 24. 17:09

문제

 

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

 

2573번: 빙산

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을

www.acmicpc.net

 

 

풀이

 

문제를 제대로 안읽어서 오래걸렸다...

 

빙산이 두 개로 나눠져있는지 체크하기 위해서는 이전에 풀었던 영역 구하는 문제들을 생각하면 된다. 빙산이 두 덩어리로 분리된다는 말은 bfs를 돌렸을때 두 번 돈다는 얘기이다.

 

이 문제를 풀 때, 전체 빙산 배열을 이중 반복문으로 하나씩 확인해가면서 방문한 적이 없고, 0이 아닌 칸에서 bfs를 통해 확인할 것이다. bfs를 진행하면서 어차피 주변의 네 곳을 전부 확인하기때문에 0의 수를 확인한 후에 그 수만큼 빼준다.

이때, 기존의 빙산 배열에서 개수를 바꾸게되면 0이 된 경우에 문제가 생긴다. 바로 다음의 케이스에서 주변의 0의 개수가 1 늘어나기 떄문이다. 

그래서 따로 값을 넣어줄 변수를 만들어줘야한다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var ice: [[Int]] = []
for _ in 0..<input[0] {
    ice.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
let zero = Array(repeating: Array(repeating: 0, count: input[1]), count: input[0])
var result = 0
outer: while true {
    var queue: [[Int]] = []
    var visited = Array(repeating: Array(repeating: false, count: input[1]), count: input[0])
    var count = 0
    var tempIce = ice
    for i in 0..<input[0] {
        for j in 0..<input[1] {
            if ice[i][j] != 0 && !visited[i][j] {
                count += 1
                if count > 1 {
                    break outer
                }
                queue.append([i,j])
                visited[i][j] = true
                while !queue.isEmpty {
                    let current = queue.removeFirst()
                    var tempCount = 0
                    for k in 0..<dx.count {
                        let newX = current[0] + dx[k]
                        let newY = current[1] + dy[k]
                        if newX < 0 || newY < 0 || newX >= input[0] || newY >= input[1] {
                            continue
                        }
                        if ice[newX][newY] == 0 {
                            tempCount += 1
                            continue
                        }
                        if !visited[newX][newY] {
                            queue.append([newX,newY])
                            visited[newX][newY] = true
                        }
                    }
                    tempIce[current[0]][current[1]] = ice[current[0]][current[1]] >= tempCount ? ice[current[0]][current[1]] - tempCount : 0
                }
            }
        }
    }
    result += 1
    if tempIce == zero {
        result = 0
        break
    }
    ice = tempIce
}
print(result)

 

 

_____________________________________________________________________________________________________

 

 

문제랑 조건을 잘 읽자..

댓글
최근에 올라온 글
Total
Today
Yesterday