[백준 2618] 경찰차 (kotlin)

🏆 문제 난이도
- Platinum IV

🔗 문제 링크
https://www.acmicpc.net/problem/2618

📝 문제 분석 & 접근

이런 유형의 문제는 단순히 현재 사건에 대해 두 경찰차 중 더 가까운 차를 보내는 탐욕적(Greedy) 접근으로는 최적의 해를 찾을 수 없습니다.

왜냐하면 당장 가까운 차를 보냈을 때, 다음 사건을 처리할 때 더 큰 손해를 볼 수 있기 때문입니다.

따라서 동적 계획법을 이용해야 합니다.

현재의 선택이 미래의 결과에 영향을 미치므로, 과거의 상태를 기억하고 최적의 선택을 이어가는 방식을 사용해야 문제를 풀 수 있습니다.

---

✨ 핵심 아이디어

사실 아이디어 자체는 매우 단순합니다.

• DP 상태 정의: dp[i][j] = 경찰차 1이 마지막으로 처리한 사건이 i, 경찰차 2가 마지막으로 처리한 사건이 j일 때, 모든 사건을 처리하는 데 필요한 최소 추가 거리.
  이때 i와 j는 사건 번호이고, 초기 출발 위치의 사건 번호를 0으로 간주합니다.
  즉, 경찰차 1의 출발지는 (1, 1), 경찰차 2의 출발지는 (n, n)입니다.
• 재귀 호출을 통한 DP 계산: dfs(targetEvent, movementOne, movementTwo) 함수를 통해 다음 사건을 어떤 차가 처리할지 결정합니다.
  - targetEvent = 현재 처리해야 할 사건 번호
  - movementOne = 경찰차 1이 마지막으로 처리한 사건 번호
  - movementTwo = 경찰차 2가 마지막으로 처리한 사건 번호

위 개념들을 사용해서 dfs 함수를 구현합니다. 

1. 경찰차 1이 targetEvent를 처리하는 경우:
   • 새로운 상태: (targetEvent, movementTwo)
   • 추가 거리: distance(movementOne, targetEvent)
2. 경찰차 2가 targetEvent를 처리하는 경우:
   • 새로운 상태: (movementOne, targetEvent)
   • 추가 거리: distance(movementTwo, targetEvent)

두 경우 중 더 짧은 거리를 선택하여 min(case1, case2)로 현재 dp 값을 갱신합니다. 이를 통해 모든 사건을 처리하는 최소 거리를 재귀적으로 계산하면 끝입니다.

 

최소 거리를 구한 후에는 어떤 경찰차가 어떤 사건을 처리했는지 경로를 역추적합니다.
이는 DP 테이블 dp를 활용하여 쉽게 할 수 있습니다.
dfs 함수 호출을 다시 따라가며, dp[i][j] 값이 어떤 선택을 통해 만들어졌는지 확인하면 됩니다.

예를 들어 dp[oneCount][twoCount]가 getDistance(true, oneCount, it+1) + dp[it + 1][twoCount]와 같다면, 이번 사건은 경찰차 1이 처리한 거라고 생각하면 됩니다.

---

💻 코드

import java.io.StreamTokenizer
import kotlin.math.*


fun main() = with(StreamTokenizer(System.`in`.bufferedReader())) {
    val sb = StringBuilder()
    fun StreamTokenizer.nextInt(): Int{
        nextToken()
        return nval.toInt()
    }

    val n = nextInt()
    val w = nextInt()
    val dp = Array(1001){ IntArray(1001) { 0 } }
    val event = Array( 1001){ Pair(0, 0) }
    repeat(w){
        event[it + 1] = Pair(nextInt(), nextInt())
    }

    fun getDistance(type: Boolean, start: Int, end: Int): Int {
        var startEvent = event[start]
        var endEvent = event[end]

        if(start == 0) startEvent = if(type) Pair(1, 1) else Pair(n, n) // 처음 위치 설정

        return abs(startEvent.first - endEvent.first) + abs(startEvent.second - endEvent.second)
    }

    fun dfs(targetEvent:Int, movementOne: Int, movementTwo: Int): Int {
        if(targetEvent > w) return 0

        if(dp[movementOne][movementTwo] != 0) return dp[movementOne][movementTwo]

        val caseOneMove = dfs(targetEvent + 1, targetEvent, movementTwo) + getDistance(true, movementOne, targetEvent)
        val caseTwoMove = dfs(targetEvent + 1, movementOne, targetEvent) + getDistance(false, movementTwo, targetEvent)

        dp[movementOne][movementTwo] = min(caseOneMove, caseTwoMove)
        return dp[movementOne][movementTwo]
    }

    sb.append(dfs(1, 0, 0)).append("\n")

    var oneCount = 0
    var twoCount = 0
    repeat(w) {
        val dist = getDistance(true, oneCount, it+1)
        if (dp[oneCount][twoCount] - dist == dp[it + 1][twoCount]) {
            oneCount = it + 1
            sb.append(1).append("\n")
        } else {
            twoCount = it + 1
            sb.append(2).append("\n")
        }
    }

    println(sb)
}