티스토리 뷰
문제
https://www.acmicpc.net/problem/2573
풀이
문제를 제대로 안읽어서 오래걸렸다...
빙산이 두 개로 나눠져있는지 체크하기 위해서는 이전에 풀었던 영역 구하는 문제들을 생각하면 된다. 빙산이 두 덩어리로 분리된다는 말은 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)
_____________________________________________________________________________________________________
문제랑 조건을 잘 읽자..
'PS' 카테고리의 다른 글
[Swift] 백준_말이 되고픈 원숭이(1600) (1) | 2023.01.25 |
---|---|
[Swift] 백준_다리 만들기(2146) (0) | 2023.01.25 |
[Swift] 백준_벽 부수고 이동하기(2206) (0) | 2023.01.22 |
[Swift] 백준_스도쿠(2580) (0) | 2023.01.21 |
[Swift] 백준_연산자 끼워넣기(14888) (0) | 2023.01.20 |
댓글
최근에 올라온 글
- Total
- Today
- Yesterday