[백준 12869번] [Kotlin] 뮤탈리스크

https://www.acmicpc.net/problem/12869

12869번: 뮤탈리스크

 

난이도 : 골드 4
태그 : 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

설명

 

뮤탈리스크가 SCV(1 ~ 3대)를 때리면

첫 타격때는 9, 둘째 타격때는 3, 셋째 타격에는 1을 줍니다.

 

이때 SCV를 모두 파괴시키는 최소 공격 횟수를 구하는 문제입니다.

 

음,,, 너비 우선 탐색으로 접근해야 할 것 같다는 느낌은 빠르게 왔는데,

어떻게 풀지 다소 난해했던 문제였습니다.

 

SCV의 초기 개수 역시 3대 고정이 아니라, 1~3대 중 하나이기 때문에

1대, 2대, 3의 경우를 각각 다 구해야 하나? 싶었지만,

생각해보니 초기 상태로 1대가 주어졌을땐 나머지 두 대의 체력을 0(파괴)으로,

초기 상태로 2대가 주어졌을 땐 나머지 한 대의 체력을 0(파괴)로 두면 될 것 같습니다.

 

 

val visited = Array(61) { Array(61) { Array(61) { -1 } } }

저는 3차원 Int 배열을 사용하여 방문 체크를 해주었는데요.

 

각 SCV의 초기 체력 값에서 시작해

뮤탈리스크가 공격할 수 있는 6가지 경우의 수의 visited를 방문체크 해줍니다.

(첫 번째 - 두 번째 - 세 번째)

(첫 번째 - 세 번째 - 두 번째)

(두 번째 - 첫 번째 - 세 번째)

(두 번째 - 세 번째 - 첫 번째)

(세 번째 - 첫 번째 - 두 번째)

(세 번째 - 두 번째 - 첫 번째)

3! = 3 * 2 * 1로, SCV를 공격하는데 6가지 경우의 수가 있습니다.

 

예를 들어, 세 SCV의 초기 체력이 12 10 4일 경우,

visited[12][10][4] = 0,

visited[9][1][3] = visited[12][10][4] + 1 = 0 + 1 = 1,   (두 번째 - 첫 번째 - 세 번째 순으로 타격)

visited[0][0][0] = visited[9][1][3] + 1 = 1 + 1 = 2,   (첫 번째 - 세 번째 - 두 번째 순으로 타격)

visited[0][0][0]을 도달하는 순간, 모든 SCV를 파괴한 것이니, 프로그램을 종료합니다.

 

 

SCV의 타격 순서의 경우,

DFS를 사용해 순열을 만들까... 아니면 그냥 하드코딩으로 6줄씩 적을까... 싶었는데,

 

2차원 배열에서 상하좌우의 이동을

dx = {0,0,1,-1}

dy = {1,-1,0,0}으로 나타냈던 것과 비슷하게

val damage = arrayOf(
    arrayOf(9, 3, 1),
    arrayOf(9, 1, 3),
    arrayOf(3, 9, 1),
    arrayOf(3, 1, 9),
    arrayOf(1, 3, 9),
    arrayOf(1, 9, 3)
)

2차원 배열 안에 공격의 경우의 수를 넣어줘 해결하였습니다.

 

 

 

소스코드

fun main() = with(System.`in`.bufferedReader()) {

    val damage = arrayOf(
        arrayOf(9, 3, 1),
        arrayOf(9, 1, 3),
        arrayOf(3, 9, 1),
        arrayOf(3, 1, 9),
        arrayOf(1, 3, 9),
        arrayOf(1, 9, 3)
    )

    val n = readLine().toInt()
    val scvInput = readLine().split(" ").map { it.toInt() }.sortedDescending().toMutableList()

    while (scvInput.size < 3) scvInput.add(0)

    val scv = scvInput.toIntArray()
    val visited = Array(61) { Array(61) { Array(61) { -1 } } }

    val q = ArrayDeque<IntArray>()
    q.add(scv)
    visited[scv[0]][scv[1]][scv[2]] = 0

    while (q.isNotEmpty()) {
        val cur = q.removeFirst()
        val copied = Array(6) { i -> IntArray(3) { j -> maxOf(0, cur[j] - damage[i][j]) } }

        copied.forEach { arr ->
            if (visited[arr[0]][arr[1]][arr[2]] != -1) return@forEach

            q.add(arr)
            visited[arr[0]][arr[1]][arr[2]] = visited[cur[0]][cur[1]][cur[2]] + 1

            if (arr.all { it == 0 }) {
                println(visited[0][0][0])
                return@with
            }
        }
    }
}

 

 

 

후기

SCV 3대를 공격하는 뮤탈리스크의 입장에서 가장 적은 공격횟수를 구하는 문제라니, 꽤나 재밌는 문제인거 같아요.

문제를 풀면서도, 이게 이렇게 푸는게 맞을까...? 싶었는데, 다행이도 통과했네요.

 

사실 위 코드는 SCV의 체력 순서가 달라지면 서로 다른 케이스로 취급하여,

(예 : visited[3][2][1], visited[2][3][1]는 서로 다른 케이스로 취급함)

더 효율적인 방문체크를 위해 매번 정렬을 할까 싶기도 했지만...

정렬을 하는데도 시간이 소요되니, 실제 실행 시간은 더 느려진 탓에

정렬 과정은 과감히 롤백했습니다.