백준 17135 캐슬 디펜스 Kotlin (시뮬레이션)

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

17135번: 캐슬 디펜스

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

입력

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

제한

• 3 ≤ N, M ≤ 15
• 1 ≤ D ≤ 10

알고리즘 분류

• 구현
• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 시뮬레이션

풀이

재밌는 문제 ㅎㅎ

재귀가 코드짤 땐 직관적이라 좋지만, 디버깅할 땐 쉽지 않다.

바로 본론으로 넘어가서 전체적인 풀이 과정은 다음과 같다.

 

1. 3명의 궁수 위치를 조합으로 선정한다. (mC3)

//본인은 nC3으로 해서 틀렸었다 ㅎㅎㅎ n과 m체크 잘 하자

2. 조합으로 선정한 궁수의 위치를 가지고 n턴만큼 시뮬레이션을 돌려본다.

//n턴 후에는 그래프에 적이 남아있지 않다.

3.1 궁수가 쏠 적을 정하는 규칙이 있다. 거리가 같으면 왼쪽 적을 공격하기 때문에 왼쪽부터 검사하다가 1을 만나면 break

3.2 궁수들은 동시에 쏘기 때문에 앞의 궁수가 1을 만나서 적을 정했다고 해도 바로 0으로 바꿔주면 안 된다. 이는 temp1, temp2 배열에
      입력에서 주어진 graph를 복사해놓아서 구현한다.(이것 때문에 temp1에 대한 복사본 temp2가 필요하다. 물론 다른 방법도 있다.)

3.3 한 턴이 끝나면(궁수 3명을 모두 검사하면) 그래프를 한 칸 내린다.(이것 때문에 입력 그래프의 복사본 temp1이 필요하다.)

 

전체적인 풀이는 위와 같은데, 여기서 이 문제의 핵심은 궁수가 쏠 적을 정하는 로직이다.

다음 그래프를 보면 쉽게 이해할 수 있을 것이다.

 

			5
		5	4	5
	5	4	3	4	5
5	4	3	2	3	4	5
4	3	2	1	2	3	4
3	2	1	궁수	1	2	3

궁수가 3열에 있다고 했을 때 적의 위치에 대한 궁수의 거리를 그래프로 나타낸 것이다.

주어진 d가 3이라고 하면,

거리가 1인 좌표들을 왼쪽, 위, 오른쪽

거리가 2인 좌표들을 왼쪽, 위, 오른쪽

거리가 3인 좌표들을 왼쪽, 위, 오른쪽

순으로 탐색하다가 1을 만나면 종료하면 되는 것이다.

이를 식으로 나타내면 다음과 같다.

for (arrange in 1 .. d) {
       for (i in -arrange .. arrange) {
             val nr = r-(arrange-kotlin.math.abs( i))
             val nc = c+i
             if (nr !in 0 until n || nc !in 0 until m) continue
      }

}

 

 

코드

val br = System.`in`.bufferedReader()
lateinit var graph: Array<IntArray>
//왼 위 오
val dir = arrayOf(arrayOf(0, -1), arrayOf(-1, 0), arrayOf(0, 1))
val archor = IntArray(3)
var answer = 0

fun down(temp1: Array<IntArray>, temp2: Array<IntArray>, n: Int, m: Int) {
    for (r in n - 1 downTo 0) {
        for (c in 0 until m) {
            var num = 0
            if (r > 0) {
                num = temp1[r - 1][c]
            }
            temp1[r][c] = num
            temp2[r][c] = num
        }
    }
}

fun solve(n: Int, m: Int, d: Int) {
    val temp1 = Array(n) { IntArray(m) }
    val temp2 = Array(n) {IntArray(m)}
    for (i in 0 until n) {
        for (j in 0 until m) {
            temp1[i][j] = graph[i][j]
            temp2[i][j] = graph[i][j]
        }
    }

    var sum = 0


    //n턴이 지나면 적이 아에 없음
    for (turn in 0 until n) {

        //3명의 궁수
        for (i in 0 until 3) {
            val c = archor[i]
            var r = n
            //d범위만큼 확인
            loop@ for (arrange in 1 .. d) {
                 for (i in -arrange .. arrange) {
                    val nr = r-(arrange-kotlin.math.abs( i))
                    val nc = c+i
                    if (nr !in 0 until n || nc !in 0 until m) continue
                    //적이 있을 때
                    if (temp1[nr][nc] == 1) {
                        if(temp2[nr][nc]==1){
                            sum++
                        }
                        temp2[nr][nc]=0
                        break@loop
                    }
                }
            }

        }
        //한 턴 끝난 후 한 칸 다운, temp2->temp1
        for(i in 0 until n){
            for(j in 0 until m){
                temp1[i][j] = temp2[i][j]
            }
        }
        down(temp1,temp2, n, m)
    }
    answer = answer.coerceAtLeast(sum)
}

//3명의 궁수 자리 선정해서 solve
fun combination(len: Int, idx: Int, n: Int, m: Int, d: Int) {
    if (len == 3) {
        solve(n, m, d)
        return
    }
    for (i in idx until m) {
        archor[len] = i
        combination(len + 1, i + 1, n, m, d)
    }
}


fun main() = with(System.out.bufferedWriter()) {

    val (n, m, d) = br.readLine().split(' ').map { it.toInt() }
    graph = Array(n) { br.readLine().split(' ').map { it.toInt() }.toIntArray() }

    combination(0, 0, n, m, d)
    write("$answer")
    close()
}