문제
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.
공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.
1초 동안 아래 적힌 일이 순서대로 일어난다.
- 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 Ar,c/5이고 소수점은 버린다.
- (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
- 공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
다음은 확산의 예시이다.
왼쪽과 위쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.
인접한 네 방향으로 모두 확산이 일어난다.
공기청정기가 있는 칸으로는 확산이 일어나지 않는다.
공기청정기의 바람은 다음과 같은 방향으로 순환한다.
방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.
입력
첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.
둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.
출력
첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.
나의 풀이
이 문제는 구현 문제로 주어진대로 차례차례 진행하면 되는 문제이다 .헷갈리기 쉬우니까 천천히 접근해야 한다. 이 문제는 다음 2단계로 나눠져 있다.
- 미세먼지 확산
- 공기청정기 작동
1. 미세먼지 확산
미세먼지가 확산되기 위해서는 미세먼지의 위치를 전부 파악하고 해당하는 위치에 모든 방향에 미세먼지를 옮겨야 한다. 다만 미세먼지는 한번에 확산됨으로 배열을 하나 더 두고 확산되는 양을 따로 저장해야 한다.
2. 공기청정기 작동
공기청정기가 작동하는 방향을 전부 구현해야 한다. 복잡하지만 천천히 접근하면 해결할 수 있다.
import java.util.*
val dx = arrayOf(1, 0, 0, -1)
val dy = arrayOf(0, 1, -1, 0)
lateinit var graph: Array<IntArray>
var robotTop = 0
var robotBottom = 0
fun main() = with(System.`in`.bufferedReader()) {
val (r, c, t) = readLine().split(" ").map { it.toInt() }
graph = Array(r) { readLine().split(" ").map { it.toInt() }.toIntArray() }
// 로봇의 위치를 찾음
for (i in 0 until r) {
if (graph[i][0] == -1 && robotBottom == 0) {
robotTop = i
robotBottom = i + 1
}
}
repeat(t) {
// 먼지의 위치를 찾음
val dust = mutableListOf<Pair<Int, Int>>()
for (i in 0 until r) {
for (j in 0 until c) {
if (graph[i][j] > 0)
dust.add(i to j)
}
}
speadDust(r, c, dust)
windCycleTop(c)
windCycleBottom(r, c)
}
var sum = 2
graph.forEach {
sum += it.sum()
}
println(sum)
}
// 먼지 확산
fun speadDust(r: Int, c: Int, dust: MutableList<Pair<Int, Int>>) {
val speadGraph = Array(r) { IntArray(c) }
dust.forEach {
val (x, y) = it
val speadAmount = graph[x][y] / 5
for (i in 0..3) {
val tempX = x + dx[i]
val tempY = y + dy[i]
if (tempX in 0 until r &&
tempY in 0 until c &&
graph[tempX][tempY] != -1) {
speadGraph[tempX][tempY] += speadAmount
graph[x][y] -= speadAmount
}
}
}
dust.forEach {
speadGraph[it.first][it.second] += graph[it.first][it.second]
}
// 그래프에 바뀐 먼지의 위치와 로봇의 위치 다시 지정
graph = speadGraph.copyOf()
graph[robotTop][0] = -1
graph[robotBottom][0] = -1
}
fun windCycleTop(c: Int) {
// [0, 0]부터 [로봇, 0]까지
for (i in robotTop - 2 downTo 0) {
graph[i + 1][0] = graph[i][0]
}
// [0, c]부터 [0, 0]까지
for (i in 0 until c - 1) {
graph[0][i] = graph[0][i + 1]
}
// [로봇, c]부터 [0, c]까지
for (i in 0 until robotTop) {
graph[i][c - 1] = graph[i + 1][c - 1]
}
// [로봇, 0]부터 [로봇, c]까지
for (i in c - 1 downTo 2) {
graph[robotTop][i] = graph[robotTop][i - 1]
}
graph[robotTop][1] = 0
}
fun windCycleBottom(r: Int, c: Int) {
// [r, 0]부터 [로봇, 0]까지
for (i in robotBottom + 1 until r - 1) {
graph[i][0] = graph[i + 1][0]
}
// [r, c]부터 [r, 0]까지
for (i in 0 until c - 1) {
graph[r - 1][i] = graph[r - 1][i + 1]
}
// [로봇, c]부터 [r, c]까지
for (i in r - 1 downTo robotBottom + 1) {
graph[i][c - 1] = graph[i - 1][c - 1]
}
// [로봇, 0]부터 [0, c]까지
for (i in c - 1 downTo 2) {
graph[robotBottom][i] = graph[robotBottom][i - 1]
}
graph[robotBottom][1] = 0
}
'백준 > 구현' 카테고리의 다른 글
20055번 - 컨베이어 벨트 위의 로봇 (0) | 2023.07.25 |
---|---|
14719번: 빗물 - Kotlin (0) | 2023.07.23 |
15685: 드래곤 커브 - Kotlin (0) | 2023.05.23 |
14890번: 경사로 - Kotlin (0) | 2023.03.29 |
14503번: 로봇 청소기 - Kotlin (0) | 2023.02.24 |