b2618. 경찰차

 

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

 

 

 

📌 자바(Java)로 푸는 경찰차 - 백준 2618 🚓🚓

두 경찰차의 최소 이동 거리 + 이동 경로까지 구하는 DP 문제

 

 

🔎 문제 개요

 

백준 2618 - 경찰차 문제는

N × N 크기의 도시에 경찰차 2대가 배치되어 있고,

여러 사건이 순차적으로 발생할 때

두 경찰차가 어떻게 사건을 분담해서

총 이동거리를 최소화할 수 있는지를 구하는 문제입니다.

 

• 경찰차 1: 항상 (1,1) 위치에서 시작
• 경찰차 2: 항상 (N,N) 위치에서 시작
• 각 사건은 정확히 한 번만 처리해야 하며,
• 각 사건은 경찰차 1 또는 경찰차 2가 처리해야 합니다.

---

💡 예제 입력

6
3
3 5
5 5
2 3

 

💡 예제 출력

9
1
2
1

 

• 총 이동거리: 9
• 각 사건을 처리한 경찰차 번호 출력

 

---

🛠 알고리즘 접근 방식

 

이 문제는 2차원 DP (Memoization) 를 활용하여

모든 가능한 사건 처리 조합을 효율적으로 탐색하는 방식으로 해결합니다.

 

---

✏️ 핵심 설계

 

• police(i, j):j번 사건을 마지막으로 처리한 경찰차 2가
• 남은 사건을 처리하는 데 드는 최소 거리
• i번 사건을 마지막으로 처리한 경찰차 1과
• dp[i][j]:
• 경찰차1이 i번, 경찰차2가 j번까지 처리했을 때의 최소 거리
• 경로 추적:역으로 추적하여 출력
• 실제로 어떤 경찰차가 어떤 사건을 처리했는지를

 

---

🔹 Java 코드 설명

 

 

📌 입력 처리

line_num = Integer.parseInt(br.readLine());
event_num = Integer.parseInt(br.readLine());

for (int i = 1; i <= event_num; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    list[i][0] = Integer.parseInt(st.nextToken());
    list[i][1] = Integer.parseInt(st.nextToken());
}

✔ 사건 정보를 list[1] ~ list[event_num]에 저장

 

 

📌 거리 계산 함수

public static int getDistance(int from, int to, int police) {
    ...
    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

✔ 경찰차가 특정 사건에서 다음 사건까지 가는 맨해튼 거리 계산

 

📌 핵심 DP 로직

public static int police(int one, int two) {
    int next = Math.max(one, two) + 1;

    if (next > event_num) return 0;
    if (dp[one][two] != 0) return dp[one][two];

    int move1 = police(next, two) + getDistance(one, next, 1);
    int move2 = police(one, next) + getDistance(two, next, 2);

    dp[one][two] = Math.min(move1, move2);
    return dp[one][two];
}

✔ 사건을 순서대로 처리하면서

✔ 다음 사건을 경찰차 1이 맡을지, 경찰차 2가 맡을지 선택

✔ 최소 거리로 갱신하며 메모이제이션

 

📌 경로 추적 로직

for (int i = 1; i <= event_num; i++) {
    int dist1 = getDistance(one, i, 1);
    int dist2 = getDistance(two, i, 2);

    if (dp[i][two] + dist1 == dp[one][two]) {
        System.out.println(1);
        one = i;
    } else {
        System.out.println(2);
        two = i;
    }
}

✔ DP 값 역추적을 통해

✔ 어떤 경찰차가 각 사건을 맡았는지 순차적으로 출력

 

---

🏆 정리

 

 

✅ 핵심 포인트

• 2차원 DP를 사용하여 상태를 나눔
  • 상태: (police1이 마지막으로 맡은 사건 번호, police2가 마지막으로 맡은 사건 번호)
• 사건을 순차적으로 처리하는 재귀 구조
• 경로 추적까지 포함된 전형적인 DP 역추적 문제