[백준 17135] - 타워디펜스(Kotlin)[골드3]

문제

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

17135번: 캐슬 디펜스

 

문제 풀이

문제가 조금 길어서 요약해 보면 다음과 같다.

• 궁수의 위치는 N행 즉 주어진 배열 한 칸 아래에 있다.
• 궁수는 3명이고, 한 칸의 한 명만 있다.
• 궁수의 사정거리는 D이하이고, 여러명의 궁수가 하나의 적을 공격할 수 있다.
• 궁수는 반드시 가장 가까운 적을 공격해야하고, 가장 가까운 적이 여러 명이라면 가장 왼쪽의 적을 공격한다.

중요한 점은 하나의 적이 여러 명의 궁수에게 공격받을 수 있다는 점이다.

여기서 카운트는 하나만 들어갈것이다. 왜냐하면 적이 하나기 때문이다.

 

문제를 읽고 든 생각이 어떻게 궁수를 효율적으로 배치할까였다.

조합을 사용해도 상관없지만, 궁수는 MC3이고 M의 최댓값이 15이기 때문에 삼중포문으로 위치를 정했다.

이렇게 3명의 궁수를 배치했다면 다음과 같은 과정을 진행한다.

1. 하나의 턴을 진행한다.
   • 하나의 턴에서 궁수들은 공격을 하고, 적들은 한 칸 내려간다.
2. 하나의 턴에서 궁수들은 공격할 수 있는 모든 적들을 배열에 저장하고, 그중에서
   가장 가깝고, 가장 왼쪽에 있는 적을 최종 적으로 판별한다.
3. 한터에서 3명의 궁수가 최종적으로 공격하는 적을 배열에서 빈칸으로 지우고, 공격한 적의 수를 +1 한다.
4. 1,2,3 반복

여기서 하나의 꼼수를 사용했다.

나는 적들을 한 칸 내리는 대신, 궁수를 한칸 올렸다.

적들을 내린다면 배열을 변경해야 하기 때문에 단순하게 궁수의 행을 한 칸 감소시켜 최소한의 변경을 목적으로 했다.

전체적인 흐름은 이러하고, 더 자세한 부분은 주석과 코드를 통해서 확인하면 될 거 같다.

 

코드

package Baekjoon.Graph.`17135`
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.abs
import kotlin.math.max
class `17135` {
    var br = BufferedReader(InputStreamReader(System.`in`))
    var row = 0
    var col = 0
    var dis = 0
    var answer = 0
    lateinit var graph : Array<Array<Int>>
    lateinit var origin : Array<Array<Int>>
    init{
        input()
        select()
        print(answer)
    }
    fun input(){
        val token = br.readLine().split(" ")
        row = token[0].toInt() // N
        col = token[1].toInt() // M
        dis = token[2].toInt() // D
        graph = Array(row) { Array(col, { 0 }) }  //원래배열
        origin = Array(row) { Array(col, { 0 }) } //복사할 배열

        for(i in 0 until  row){
            val line = br.readLine().split(" ")
            for(j in 0 until  col){
                graph[i][j] = line[j].toInt()
                origin[i][j] = graph[i][j]
            }
        }
    }
    fun loadOrigin(){ //한번 실행시킨 배열을 원래 배열로 다시 바꾸는 작업
        for(i in 0 until row){
            for(j in 0 until col){
                graph[i][j]=origin[i][j]
            }
        }
    }
    fun select(){ //궁수의 위치를 선택하는 작업.
        for(i in 0 until col){
            for( j in i+1 until col){
                for(k in j+1 until  col){
                    answer = max(answer,attack(i,j,k))
                    loadOrigin()
                }
            }
        }
    }
    fun attack(one : Int,two:Int,three : Int) : Int{ //궁수의 위치는 (N,one) , (N,two), (N,three)
        var arc : MutableList<Int> = mutableListOf()
        var result=0
        arc.apply { //궁수의 위치를 넣어줌.
            add(one)
            add(two)
            add(three)
        }
        var loc = row //궁수가 초기 위치한 행은 맨 밑임.
        while(loc>=1) { //종료조건 : 적이 한칸 내리는 대신 궁수를 한칸씩 올려서 끝까지 함.
            val target : MutableList<Triple<Int,Int,Int>> = mutableListOf()
            for (peo in arc) {
                var enemy : MutableList<Triple<Int,Int,Int>> = mutableListOf()
                for (i in 0 until loc) {
                    for (j in 0 until col) {
                        if (graph[i][j] != 1) //적이 아닐 경우
                            continue
                        val enemyDis = dist(Pair(loc,peo),Pair(i,j))
                        if(enemyDis>dis) //거리가 크다면
                            continue
                        enemy.add(Triple(i,j,enemyDis)) //배열에 적의 위치와 거리를 같이 넣음.
                    }
                }
                if(enemy.isEmpty()) continue //적이 비어있다면 궁수는 공격할 적이 없다는 뜻.
                enemy.sortWith(compareBy({ it.third }, { it.second })) //적을 거리순으로 오름차순후, 같은 거리라면 열로 오름차순함.
                target.add(enemy.first()) //가장 가깝고 왼쪽에 있는 적을 공격
            }
            for(ele in target){  //여기서는 중복된 적을 공격할수도 있기에, 아래와 같이 검사함.
                if(graph[ele.first][ele.second]==1) { //적일 경우
                    graph[ele.first][ele.second]=0
                    result++
                }
            }
            loc-- //궁수를 한칸 올림.
        }
        return result
    }
    fun dist(me : Pair<Int,Int>, side : Pair<Int,Int>) : Int{ //거리를 구하는 함수
        return abs(me.first-side.first) + abs(me.second-side.second)
    }
}
fun main(){
    var solution = `17135`()
}

---

다른 사람의 코드를 푸니 대부분 재귀를 사용한 조합을 구현해서 궁수를 배치했다.

재귀를 사용한 조합을 구현할 줄 알아야 다른 문제를 풀 때 유리할 거 같네..