[백준 17135번] [Kotlin] 캐슬 디펜스

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

17135번: 캐슬 디펜스

 

난이도 : 골드 3
태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 시뮬레이션, 너비 우선 탐색

 

 

설명

다들 한 번쯤은 해봤을 법한 디펜스 게임을 구현하는 문제네요.

궁수의 위치를 선택해야 했기 때문에 백트래킹을 사용한 수열 구하기를 사용해야하나? 싶었는데,

생각해보니 궁수는 3명으로 고정되어 있으므로, 굳이 백트래킹을 사용하지 않아도 3중 for문으로 간단히 가능합니다.

 

또, 가장 가까운 적의 위치를 찾고, 해당 적의 위치가 여러 군데일 경우, 왼쪽을 우선탐색 합니다.

저 같은 경우는

dx = { 0, -1, 0 }

dy = {-1 , 0, 1} 과 같이 지정하여 왼쪽을 우선탐색 하였습니다.

화살이 밑으로 가지는 않으므로 dx가 +1인 경우는 넣지 않아도 됩니다.

 

 

 

접근방법

1. 3중 for문으로 궁수 3명의 위치를 선택한다.

-- 2 - 1. 게임 시작

---- 3 - 1. 턴 시작

---- 3 - 2. 각각의 궁수에 대해 BFS를 사용해 가장 가까운 적의 위치를 찾는다.

----  (주의사항) 탐색 순서는 왼쪽 우선 탐색이며, dy를 (-1, 0, 1)로 지정하여 처리한다.

----  (주의사항) 여러 궁수가 한 적을 맞출 수도 있기 때문에, 적을 찾고 바로 제거하는 것이 아닌 모든 궁수가 활을 쏜 뒤 적을 제거해야 한다.

---- 3 - 3. 모든 궁수가 화살을 쐈다면 적들의 위치를 1만큼 내린다.

---- 3 - 4. 적이 아직 남아있다면 3-1번으로 돌아간다.

-- 2 - 2. 적이 모두 제거되면 1번으로 돌아가 다음 궁수의 위치 조합으로 시뮬레이션을 돌려본다.

 

 

 

소스코드

전체 소스코드

import java.util.ArrayDeque
import java.util.StringTokenizer

data class Node(val x: Int, val y: Int)

val dx = intArrayOf(0, -1, 0) // 화살은 아래로 쏘지 않음
val dy = intArrayOf(-1, 0, 1) // 왼쪽 우선 탐색
var n = 0
var m = 0
var d = 0

fun main() = with(System.`in`.bufferedReader()) {
    val nmd = readLine().split(" ").map { it.toInt() }
    n = nmd[0]
    m = nmd[1]
    d = nmd[2]

    val map = Array(n) { IntArray(m) }

    repeat(n) { x ->
        val st = StringTokenizer(readLine())
        repeat(m) { y ->
            map[x][y] = st.nextToken().toInt()
        }
    }

    var maxScore = 0

    for (i in 0..<m - 2) {
        for (j in i + 1..<m - 1) {
            for (k in j + 1..<m) {
                val copiedMap = Array(n) { x -> IntArray(m) { y -> map[x][y] } }
                val archerPoints = listOf(i, j, k)

                val score = playGame(archerPoints, copiedMap)
                maxScore = maxOf(maxScore, score)
            }
        }
    }

    println(maxScore)
}

fun playGame(archerPoints: List<Int>, map: Array<IntArray>): Int {
    var score = 0

    while (!gameIsEnd(map)) {
        score += playTurn(archerPoints, map)
        enemyMove(map)
    }

    return score
}

fun playTurn(archerPoints: List<Int>, map: Array<IntArray>): Int {
    val killedEnemy = HashSet<Node>()

    archerPoints.forEach { archerPoint ->
        shoot(archerPoint, map, killedEnemy)
    }

    killedEnemy.forEach { node ->
        map[node.x][node.y] = 0
    }

    return killedEnemy.size
}

fun shoot(archerPoint: Int, map: Array<IntArray>, killedEnemy: HashSet<Node>) {
    val queue = ArrayDeque<Node>()
    queue.add(Node(n, archerPoint))

    val visited = Array(n + 1) { IntArray(m) }

    while (queue.isNotEmpty()) {
        val cur = queue.poll()

        for (i in 0..<3) {
            val nx = cur.x + dx[i]
            val ny = cur.y + dy[i]
            val nd = visited[cur.x][cur.y] + 1

            if (nx !in 0..<n || ny !in 0..<m || nd > d) continue

            if (map[nx][ny] == 1) {
                killedEnemy.add(Node(nx, ny))
                return
            }

            queue.add(Node(nx, ny))
            visited[nx][ny] = nd
        }
    }
}


fun gameIsEnd(map: Array<IntArray>) = map.all { it.all { it == 0 } }

fun enemyMove(map: Array<IntArray>) {
    for (i in n - 1 downTo 1) {
        map[i] = map[i - 1]
    }
    map[0] = IntArray(m) { 0 }
}

 

 

 

궁수 3명의 위치 조합

for (i in 0..<m - 2) {
    for (j in i + 1..<m - 1) {
        for (k in j + 1..<m) {
            val copiedMap = Array(n) { x -> IntArray(m) { y -> map[x][y] } }
            val archerPoints = listOf(i, j, k)

            val score = playGame(archerPoints, copiedMap)
            maxScore = maxOf(maxScore, score)
        }
    }
}

 

배치할 궁수는 항상 3명이므로, 백트래킹을 통해 조합을 조합을 구할 필요 없이 3중 for문으로 쉽게 구현 가능합니다.

각각의 궁수 위치 조합을 구한 뒤, playGame 메서드를 호출해 해당 궁수 조합으로 게임을 실행합니다.

 

 

playGame

fun playGame(archerPoints: List<Int>, map: Array<IntArray>): Int {
    var score = 0

    while (!gameIsEnd(map)) {
        score += playTurn(archerPoints, map)
        enemyMove(map)
    }

    return score
}

 

각 턴을 실행하고(playTurn 메서드), 적들을 한 칸씩 내립니다 (enemyMove 메서드)

두 과정을 게임이 모두 끝날 때(gameIsEnd 메서드)까지 반복합니다.

 

 

playTurn

fun playTurn(archerPoints: List<Int>, map: Array<IntArray>): Int {
    val killedEnemy = HashSet<Node>()

    archerPoints.forEach { archerPoint ->
        shoot(archerPoint, map, killedEnemy)
    }

    killedEnemy.forEach { node ->
        map[node.x][node.y] = 0
    }

    return killedEnemy.size
}

 

각 궁수들의 위치에서 활을 쏩니다. (shoot)

단, 여러 궁수가 하나의 적을 맞출 수도 있기 때문에 바로 제거하는 것이 아닌 모든 궁수가 활을 쏜 뒤 적을 맵에서 제거해야 합니다.

같은 적을 맞출 수 있기 때문에 중복을 제거하기 위해 Set을 사용하였습니다.

 

 

shoot

fun shoot(archerPoint: Int, map: Array<IntArray>, killedEnemy: HashSet<Node>) {
    val queue = ArrayDeque<Node>()
    queue.add(Node(n, archerPoint))

    val visited = Array(n + 1) { IntArray(m) }

    while (queue.isNotEmpty()) {
        val cur = queue.poll()

        for (i in 0..<3) {
            val nx = cur.x + dx[i]
            val ny = cur.y + dy[i]
            val nd = visited[cur.x][cur.y] + 1

            if (nx !in 0..<n || ny !in 0..<m || nd > d) continue

            if (map[nx][ny] == 1) {
                killedEnemy.add(Node(nx, ny))
                return
            }

            queue.add(Node(nx, ny))
            visited[nx][ny] = nd
        }
    }
}

 

shoot은 bfs로 가장 가까운 적들을 찾는 메서드입니다.

궁수의 사정거리 이내에서 적을 찾으면 killedEnemy에 넣어주고 return 합니다.

 

 

 

후기

문제 이해와 아이디어는 빠르게 떠올렸지만, 구현 과정에 다소 시간이 걸렸던 문제였던 것 같습니다.

역시 그래프 탐색은 언제해도 재밌습니다!