백준 23289 온풍기 안녕! Kotlin (시뮬레이션)

문제 출처 : https://www.acmicpc.net/problem/23289

23289번: 온풍기 안녕!

유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기

www.acmicpc.net

문제

유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)의 온도를 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

구사과의 성능 테스트는 다음과 같은 작업이 순차적으로 이루어지며, 가장 처음에 모든 칸의 온도는 0이다. 문제의 그림에서 빈 칸은 온도가 0인 칸을 의미한다.

집에 있는 모든 온풍기에서 바람이 한 번 나옴
온도가 조절됨
온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
초콜릿을 하나 먹는다.
조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.

집에 있는 모든 온풍기에서 바람이 한 번 나오는 과정을 설명하면 다음과 같다.

<그림 1>

<그림 1>은 크기가 7×8인 집에 온풍기가 (3, 1)에 설치되어 있는 상황이다. 온풍기는 바람이 나오는 방향이 있는데, 그 방향은 오른쪽, 왼쪽, 위, 아래 중 하나이다. 온풍기에서 따뜻한 바람이 한 번 나오면, 다음과 같은 영역의 온도가 칸에 적힌 값만큼 증가하게 된다. 아래 그림은 오른쪽 방향으로 바람이 나온 예시이며, 온풍기에서 바람이 나오는 방향에 따라 <그림 2>를 회전시켜서 해당하는 방향으로 바람이 나왔을 때 증가하는 온도를 구할 수 있다.

<그림 2>

온풍기에서 바람이 한 번 나왔을 때, 온풍기의 바람이 나오는 방향에 있는 칸은 항상 온도가 5도 올라간다. 그 다음 이 바람은 계속 다른 칸으로 이동해 다른 칸의 온도를 위의 그림과 같이 상승시키게 된다. 어떤 칸 (x, y)에 온풍기 바람이 도착해 온도가 k (> 1)만큼 상승했다면, (x-1, y+1), (x, y+1), (x+1, y+1)의 온도도 k-1만큼 상승하게 된다. 이때 그 칸이 존재하지 않는다면, 바람은 이동하지 않는다. 온풍기에서 바람이 한 번 나왔을 때, 어떤 칸에 같은 온풍기에서 나온 바람이 여러 번 도착한다고 해도 온도는 여러번 상승하지 않는다.

<그림 1>의 상태에서 온풍기 바람이 한 번 불었다면, 증가하는 온도의 양은 <그림 3>과 같다.

<그림 3>

일부 칸과 칸 사이에는 벽이 있어 온풍기 바람이 지나갈 수 없다. 바람이 오른쪽으로 불었을 때 어떤 칸 (x, y)에서 (x-1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x-1, y) 사이에 벽이 없어야 하고, (x-1, y)와 (x-1, y+1) 사이에도 벽이 없어야 한다. (x, y)에서 (x, y+1)로 바람이 이동할 수 있으려면 (x, y)와 (x, y+1) 사이에 벽이 없어야 한다. 마지막으로 (x, y)에서 (x+1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x+1, y), (x+1, y)와 (x+1, y+1) 사이에 벽이 없어야 한다.

예를 들어, (3, 4)와 (3, 5) 사이에 벽이 있는 경우 온풍기에서 바람이 한 번 나왔을 때 온도는 <그림 4>와 같이 상승한다. 벽은 빨간색으로 표시했다.

<그림 4>

(3, 5)는 (3, 4), (2, 4), (4, 4)에서 바람이 이동할 수 없기 때문에, 온도가 상승하지 않는다.

만약 바람의 방향이 왼쪽인 온풍기가 (4, 7)에 있고, (3, 4)와 (3, 5) 사이에 벽, (2, 5)와 (3, 5) 사이에 벽이 있는 경우라면 온풍기에서 바람이 한 번 나왔을 때 <그림 5>와 같이 온도가 상승한다. <그림 6>은 바람의 방향이 아래인 온풍기가 (2, 5)에 있고, (4, 4)와 (4, 5) 사이, (4, 4)와 (5, 4) 사이, (4, 6)과 (5, 6) 사이에 벽이 있는 경우이다.

구사과의 집에는 온풍기가 2대 이상 있을 수도 있다. 이 경우 각각의 온풍기에 의해서 상승한 온도를 모두 합한 값이 해당 칸의 상승한 온도이다.

예를 들어, <그림 7>은 <그림 6>과 같은 벽을 가지고 있는 집에서 바람이 방향이 위인 온풍기가 (7, 5)에 있는 경우이고, <그림 8>는 <그림 6>과 같은 벽을 가지고 있는 집에서 바람의 방향이 아래인 온풍기가 (2, 5)에 있고, 바람의 방향이 위인 온풍기가 (7, 5)에 있는 경우이다. <그림 8>는 같은 벽을 가지고 있는 집에서 <그림 6>의 온풍기와 <그림 7>의 온풍기가 동시에 설치된 상황이기 때문에, 각 칸의 상승한 온도는 두 그림의 값을 더한 값과 같다. 온풍기가 있는 칸도 다른 온풍기에 의해 온도가 상승할 수 있기 때문에, <그림 8>에서 온풍기의 위치는 표시하지 않았다.

온도가 조절되는 과정은 다음과 같다.

모든 인접한 칸에 대해서, 온도가 높은 칸에서 낮은 칸으로 ⌊(두 칸의 온도의 차이)/4⌋만큼 온도가 조절된다. 온도가 높은 칸은 이 값만큼 온도가 감소하고, 낮은 칸은 온도가 상승한다. 인접한 두 칸 사이에 벽이 있는 경우에는 온도가 조절되지 않는다. 이 과정은 모든 칸에 대해서 동시에 발생한다.

다음은 온도 조절의 예시이다.

(1, 1)에서 (1, 2)와 (1, 3)으로 공기가 섞인다.

(2, 2)와 (3, 2) 사이에 벽이 있기 때문에, (3, 2)는 온도가 그대로 유지된다.

모든 칸에 대해서 동시에 온도의 조절이 발생한다.

가장 바깥쪽 칸은 1행, R행, 1열, C열에 있는 칸이다. 예를 들어, <그림 9>와 같은 경우 가장 바깥쪽 칸의 온도가 1씩 감소하면 <그림 10>과 같이 된다. 온도가 0인 칸은 온도가 감소하지 않는다.

방의 크기와 방에 설치된 온풍기의 정보, 벽의 위치와 조사하려고 하는 칸의 위치가 주어진다. 구사과가 먹은 초콜릿의 개수를 출력한다.

입력

첫째 줄에 세 정수 R, C, K가 주어진다. 둘째 줄부터 R개의 줄에 방의 정보가 주어진다. i번째 줄의 j번째 정수는 (i, j)의 정보를 의미하며 다음 중 하나이다.

0: 빈 칸
1: 방향이 오른쪽인 온풍기가 있음
2: 방향이 왼쪽인 온풍기가 있음
3: 방향이 위인 온풍기가 있음
4: 방향이 아래인 온풍기가 있음
5: 온도를 조사해야 하는 칸

다음 줄에는 벽의 개수 W가 주어진다. 다음 W개의 줄에는 벽의 정보가 주어지며, 이 정보는 세 정수 x, y, t로 이루어져 있다. t가 0인 경우 (x, y)와 (x-1, y) 사이에 벽이 있는 것이고, 1인 경우에는 (x, y)와 (x, y+1) 사이에 벽이 있는 것이다.

출력

구사과가 먹는 초콜릿의 개수를 출력한다. 만약, 먹는 초콜릿의 개수가 100을 넘어가면 101을 출력한다.

제한

2 ≤ R, C ≤ 20
1 ≤ K ≤ 1,000
온풍기는 하나 이상 있고, 온도를 조사해야 하는 칸도 하나 이상 있다.
0 ≤ W ≤ R×C
1 < x ≤ R, 1 ≤ y ≤ C (t = 0)
1 ≤ x ≤ R, 1 ≤ y < C (t = 1)
온풍기가 있는 칸과 바람이 나오는 방향에 있는 칸 사이에는 벽이 없다.
온풍기의 바람이 나오는 방향에 있는 칸은 항상 존재한다.
같은 벽이 두 번 이상 주어지는 경우는 없다.

알고리즘 분류

풀이

삼성 구현 문제다.

벽을 잘 저장하면 난이도가 확 내려간다.

우선 전체적인 흐름은 다음과 같다.

1. 온풍기 위치, 방향 저장

2. 벽의 위치,방향 저장

3. 온풍기 쏘기 (벽 고려)

4. 온도 조절 (벽 고려)

5. 테두리 온도 -1

6. 조사하는 칸의 온도가 모두 k이상인지 검사, k이상이 아니라면 위의 과정 반복

문제가 길기 때문에 온풍기와 벽의 관계에 대해 자세히 봐야 한다.

본인은 이 부분을 잘못 이해해서 삽질했다.

우리는 방향에따라 온풍기의 바람이 이동하는 칸도 다르고 검사해야 하는 벽도 다르다.

방향은 우좌상하로 총 4가지인데, 이때마다 4가지 방향 모두 분기 처리하면 코드도 너무 길어지고 실수하기 쉽다.

따라서 dx,dy 테크닉으로 이동에 대해서 분기를 줄이고, 벽을 방향으로 저장하는 것이 아닌, 4차원 배열로 저장한다.

walls[r1][c1][r2][c2] = r1,c1과 r2,c2 사이의 벽이 있는지

fun tempControl() {
    val temp = Array(R) { IntArray(C) }
    for (r in 0 until R) {
        for (c in 0 until C) {
            for (i in 1..4) {
                val nr = r + dir[i][0]
                val nc = c + dir[i][1]
                if (nr !in 0 until R || nc !in 0 until C) continue
                if (walls[r][c][nr][nc]) continue
                val diff = map[r][c] - map[nr][nc]
                if (diff > 0) {
                    temp[r][c] -= diff / 4
                    temp[nr][nc] += diff / 4
                }
            }
        }
    }
    for (r in 0 until R) {
        for (c in 0 until C) {
            map[r][c] += temp[r][c]
        }
    }
}

우선 온도 조절 코드이다.

온도 조절은 주어진 조건대로 인접한 4방향에 대해 두 좌표 사이 차이값/4를 더하고 뺀다.

이러한 계산은 이전 상태를 유지하다가 일괄적으로 계산되는 것에 유의하자.

val dxdy = arrayOf(
    arrayOf(),
    arrayOf(//우
        arrayOf(0, 1),
        arrayOf(-1, 1),
        arrayOf(1, 1)
    ),
    arrayOf(//좌
        arrayOf(0, -1),
        arrayOf(-1, -1),
        arrayOf(1, -1)
    ),
    arrayOf(//상
        arrayOf(-1, 0),
        arrayOf(-1, 1),
        arrayOf(-1, -1)
    ),
    arrayOf(//하
        arrayOf(1, 0),
        arrayOf(1, 1),
        arrayOf(1, -1)
    )
)

fun isWall(r: Int, c: Int, nr: Int, nc: Int, d: Int): Boolean {
    if(r == nr || c == nc){
        return walls[r][c][nr][nc]
    }
    //우좌
    if(d<=2){
        return walls[r][c][nr][c] || walls[nr][c][nr][nc]
    }
    //상하
    else{
        return walls[r][c][r][nc] || walls[r][nc][nr][nc]
    }
}

fun wind(r: Int, c: Int, d: Int) {

    val q: Queue<Pair<Int, Int>> = LinkedList()
    val visited = Array(R) { BooleanArray(C) }
    val x = r + dxdy[d][0][0]
    val y = c + dxdy[d][0][1]
    if (x !in 0 until R || y !in 0 until C) return
    q.add(Pair(x, y))
    map[x][y] += 5
    var depth = 4
    while (q.isNotEmpty()) {
        val size = q.size
        for (i in 0 until size) {
            val (cr, cc) = q.poll()
            for (j in 0 until 3) {
                val nr = cr + dxdy[d][j][0]
                val nc = cc + dxdy[d][j][1]
                if (nr !in 0 until R || nc !in 0 until C) continue
                if (visited[nr][nc]) continue
                if (isWall(cr, cc,nr,nc, d)) continue
                visited[nr][nc] = true
                map[nr][nc] += depth
                if (depth == 1) continue
                q.add(Pair(nr, nc))
            }
        }
        depth--
    }
}

다른 부분은 어렵지 않다.

온풍기의 바람을 이동시키는 부분이 핵심이다.

wind()함수가 하나의 온풍기 바람을 이동시키는 함수인데, bfs로 구현했다.

dx,dy로 온풍기의 방향에 따라 3가지 탐색 루트를 다르게 주었고, 이 탐색 루트로 visit체크, 벽 체크하며 탐색했다.

벽인지 체크하는 함수도 a좌표->b좌표로 가는 데 벽이 있는지 저장해두었기 때문에, 탐색에 있어서 현재 좌표, 다음 좌표를 이용해

우좌/상하 방향에 따라 벽 체크를 쉽게 할 수 있다.

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

var R = 0
var C = 0
var K = 0
var W = 3

//1우
//2좌
//3상
//4하
val dir = arrayOf(
    intArrayOf(),
    intArrayOf(0, 1),
    intArrayOf(0, -1),
    intArrayOf(-1, 0),
    intArrayOf(1, 0)
)

val dxdy = arrayOf(
    arrayOf(),
    arrayOf(//우
        arrayOf(0, 1),
        arrayOf(-1, 1),
        arrayOf(1, 1)
    ),
    arrayOf(//좌
        arrayOf(0, -1),
        arrayOf(-1, -1),
        arrayOf(1, -1)
    ),
    arrayOf(//상
        arrayOf(-1, 0),
        arrayOf(-1, 1),
        arrayOf(-1, -1)
    ),
    arrayOf(//하
        arrayOf(1, 0),
        arrayOf(1, 1),
        arrayOf(1, -1)
    )
)

lateinit var walls: Array<Array<Array<BooleanArray>>>
lateinit var map: Array<IntArray>
val airStart = ArrayList<Triple<Int, Int, Int>>()
val destination = ArrayList<Pair<Int, Int>>()

fun canFinish(): Boolean {
    for (des in destination) {
        val (r, c) = des
        if (map[r][c] < K) return false
    }
    return true
}

fun sideMinus() {
    for (r in 0 until R) {
        if (map[r][0] > 0) map[r][0]--
        if (map[r][C - 1] > 0) map[r][C - 1]--
    }
    for (c in 1 until C - 1) {
        if (map[0][c] > 0) map[0][c]--
        if (map[R - 1][c] > 0) map[R - 1][c]--
    }
}

fun isWall(r: Int, c: Int, nr: Int, nc: Int, d: Int): Boolean {
    if(r == nr || c == nc){
        return walls[r][c][nr][nc]
    }
    //우좌
    if(d<=2){
        return walls[r][c][nr][c] || walls[nr][c][nr][nc]
    }
    //상하
    else{
        return walls[r][c][r][nc] || walls[r][nc][nr][nc]
    }
}

fun wind(r: Int, c: Int, d: Int) {

    val q: Queue<Pair<Int, Int>> = LinkedList()
    val visited = Array(R) { BooleanArray(C) }
    val x = r + dxdy[d][0][0]
    val y = c + dxdy[d][0][1]
    if (x !in 0 until R || y !in 0 until C) return
    q.add(Pair(x, y))
    map[x][y] += 5
    var depth = 4
    while (q.isNotEmpty()) {
        val size = q.size
        for (i in 0 until size) {
            val (cr, cc) = q.poll()
            for (j in 0 until 3) {
                val nr = cr + dxdy[d][j][0]
                val nc = cc + dxdy[d][j][1]
                if (nr !in 0 until R || nc !in 0 until C) continue
                if (visited[nr][nc]) continue
                if (isWall(cr, cc,nr,nc, d)) continue
                visited[nr][nc] = true
                map[nr][nc] += depth
                if (depth == 1) continue
                q.add(Pair(nr, nc))
            }
        }
        depth--
    }
}

fun tempControl() {
    val temp = Array(R) { IntArray(C) }
    for (r in 0 until R) {
        for (c in 0 until C) {
            for (i in 1..4) {
                val nr = r + dir[i][0]
                val nc = c + dir[i][1]
                if (nr !in 0 until R || nc !in 0 until C) continue
                if (walls[r][c][nr][nc]) continue
                val diff = map[r][c] - map[nr][nc]
                if (diff > 0) {
                    temp[r][c] -= diff / 4
                    temp[nr][nc] += diff / 4
                }
            }
        }
    }
    for (r in 0 until R) {
        for (c in 0 until C) {
            map[r][c] += temp[r][c]
        }
    }
}

fun simulation() {
    //온풍기 시뮬레이션
    for (air in airStart) {
        wind(air.first, air.second, air.third)
    }
//    //온도 조절
    tempControl()
    //테두리 온도 -1
    sideMinus()
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    getIntList().apply {
        R = this[0]
        C = this[1]
        K = this[2]
    }
    //온풍기, 감시 구간 입력
    for (r in 0 until R) {
        val line = getIntList()
        for (c in 0 until C) {
            if (line[c] != 0) {
                if (line[c] == 5) {
                    destination.add(Pair(r, c))
                } else {
                    airStart.add(Triple(r, c, line[c]))
                }
            }
        }
    }
    //벽 입력
    W = getInt()
    walls = Array(R) { Array(C) { Array(R) { BooleanArray(C) } } }
    map = Array(R) { IntArray(C) }
    repeat(W) {
        val wall = getIntList()
        val r = wall[0] - 1
        val c = wall[1] - 1
        //가로벽
        if (wall[2] == 0) {
            walls[r][c][r-1][c] = true
            walls[r-1][c][r][c] = true
        }
        //세로벽
        else {
            walls[r][c][r][c+1] = true
            walls[r][c + 1][r][c] = true
        }

    }

    //solve
    var cnt = 0
    while (cnt <= 100) {
        cnt++
        simulation()
        //끝났는지 확인
        if (canFinish()) break
    }

    write("$cnt")
    close()
}

저작자표시

'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글

백준 1022 소용돌이 예쁘게 출력하기 Kotlin (구현) (0)	2022.07.04
백준 14891 톱니바퀴 Kotlin (구현) (0)	2022.07.03
백준 18115 카드 놓기 Kotlin (덱) (0)	2022.06.30
백준 2118 두 개의 탑 Kotlin (투 포인터 + 이분 탐색) (0)	2022.06.29
백준 20007 떡 돌리기 Kotlin (다익스트라) (0)	2022.06.28

옹벨 일기

백준 23289 온풍기 안녕! Kotlin (시뮬레이션)

문제

입력

출력

제한

알고리즘 분류

풀이

코드

'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글

댓글

티스토리툴바

백준 23289 온풍기 안녕! Kotlin (시뮬레이션)

문제

입력

출력

제한

알고리즘 분류

풀이

코드

'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글

관련글

댓글

티스토리툴바