[ 알고리즘 / Kotlin ] 백준 17144 미세먼지 안녕!

안녕하세요 gyub(귭)입니다 ㅎㅎㅎ

이번 문제는 미세먼지 안녕!!!!입니다

 

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

 

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

인접한 네 방향으로 모두 확산이 일어난다.

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

 

처음에 문제를 봤을 때 잘 이해가 안 갔는데 예시가 잘 나와있어서 다행이었어요 ㅎ

 

 

접근방법

의외로 간단한 문제였어요! 문제에서 주어진 조건만 순서대로 실행시키면 되는데여

간단하게 정리해보자면

 

첫 번째, 미세먼지를 확장시킨다.

1) 모든 부분을 탐색하며 각 부분의 네 방향을 탐색하며

2) 확산 시킬 수 있는 곳이면 ( 공기청정기가 없어나 배열 안 영역일 때)

3) 해당 부분의 값/5 를 각 방향에 더해줌과 동시에 해당부분의 값에서 빼줍시다!

 

두 번째, 공기청정기

1) 미세먼지를 완전히 확장시킨 후

2) 공기청정기의 윗 부분과 아랫 부분을 나눠

3) 미세먼지를 반시계방향, 시계방향으로 값을 돌립(?)니다

4) 주의할 점은 공기청정기에 들어가면 미세먼지의 값이 0이 되어 나와요!

 

코드

코드를 보시는게 더 이해가 잘 갈 것 같긴하네요 ㅎ

 

 

미세먼지를 확산시키거나 공기청정기를 돌릴때 각각 동시에 이뤄지므로 임시배열을 생성합니다.

private fun deepCopy(r: Int, c: Int): Array<IntArray> {
    var tmp = Array(r) { IntArray(c) }
    for (i in 0 until r) {
        for (j in 0 until c) {
            tmp[i][j] = arr[i][j]
        }
    }
    return tmp
}

 

미세먼지 확산

private fun spreadDust(r: Int, c: Int) {
    val tmpArr = deepCopy(r, c)

    for (i in 0 until r) {
        for (j in 0 until c) {
            val dust = tmpArr[i][j] / 5
            for (k in 0 until 4) {
                val (curX, curY) = intArrayOf(i + goX[k], j + goY[k])
                if (curX < 0 || curX >= r || curY < 0 || curY >= c) continue
                if (curX == air[0].first && curY == air[0].second) continue
                if (curX == air[1].first && curY == air[1].second) continue
                arr[curX][curY] += dust
                arr[i][j] -= dust
            }
        }
    }

}

공기청정기

private fun moveDust(r: Int, c: Int) {
    val tmpArr = deepCopy(r, c)
    // 윗칸
    for (i in 0..air[0].first) {
        for (j in 0 until c) {

            // 맨 위
            if (i == 0) {
                if (j == c - 1) arr[i][j] = tmpArr[i + 1][j]
                else arr[i][j] = tmpArr[i][j + 1]
            }
            // 맨 아래
            else if (i == air[0].first) {
                if (j == 0) arr[i][j] = tmpArr[i - 1][j]
                else arr[i][j] = tmpArr[i][j - 1]
            }
            // 맨 왼쪽
            else if (j == 0) {
                if (i == 0) arr[i][j] = tmpArr[i][j + 1]
                else arr[i][j] = tmpArr[i - 1][j]
            }
            // 맨 오른쪽
            else if (j == c - 1) {
                if (i == air[0].first) arr[i][j] = tmpArr[i][j - 1]
                else arr[i][j] = tmpArr[i + 1][j]
            }
        }
    }
    // 청정기 아랫칸
    for (i in air[1].first until r) {
        for (j in 0 until c) {
            // 맨 위
            if (i == air[1].first) {
                if (j == 0) arr[i][j] = tmpArr[i + 1][j]
                else arr[i][j] = tmpArr[i][j - 1]
            }
            // 맨 아래
            else if (i == r - 1) {
                if (j == c - 1) arr[i][j] = tmpArr[i - 1][j]
                else arr[i][j] = tmpArr[i][j + 1]
            }
            // 맨 왼쪽
            else if (j == 0) {
                if (i == r - 1) arr[i][j] = tmpArr[i][j + 1]
                else arr[i][j] = tmpArr[i + 1][j]
            }
            // 맨 오른쪽
            else if (j == c - 1) {
                if (i == air[1].first) arr[i][j] = tmpArr[i][j - 1]
                else arr[i][j] = tmpArr[i - 1][j]
            }
        }
    }
    // 공기 정화
    arr[air[0].first][air[0].second] = 0
    arr[air[1].first][air[1].second] = 0


}

 

 

 

전체 코드

github.com/Songgyubin/Algorithm/blob/master/baekjoon/BOJ_17144.kt

봐주셔서 감사합니다!
질문이나 수정되어야 할 부분이 있다면 댓글로 남겨주세요!