Jerry Kim

42는 ‘The Hitchhiker’s Guide to the Galaxy’라는 SF 소설에서 삶, 우주, 그리고 모든 것에 대한 궁극적인 질문에 대한 해답이다.

8 minute read

경찰차들은 도시의 여러 사건을 처리하기 위해 최적의 경로를 찾아야 한다. 이때 두 대의 경찰차가 이동한 거리의 합을 최소화하는 것이 목표이다. 도시의 구조와 사건의 발생 위치가 주어졌을 때, 어떻게 하면 두 경찰차의 총 이동 거리를 최소화할 수 있을까?

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

문제 설명

도시는 N x N 크기의 격자 형태로 이루어져 있으며, 각 도로는 동서방향과 남북방향으로 구분된다. 동서방향 도로는 위에서부터 1부터 N까지 번호가 매겨지고, 남북방향 도로는 왼쪽에서부터 1부터 N까지 번호가 매겨진다. 도로들이 교차하는 지점은 (동서방향 도로 번호, 남북방향 도로 번호)로 표시된다.

두 대의 경찰차가 있으며, 경찰차 1은 (1, 1) 위치에서, 경찰차 2는 (N, N) 위치에서 출발한다. W개의 사건이 발생하며, 각 사건은 특정 위치에서 발생한다. 각 사건은 두 경찰차 중 하나가 처리해야 하며, 사건은 발생한 순서대로 처리해야 한다.

목표는 두 경찰차가 이동한 거리의 합을 최소화하면서 모든 사건을 처리하는 것이다. 사건을 어떤 경찰차가 처리할지 결정하고, 최소 이동 거리를 구하는 프로그램을 작성해야 한다.

접근 방식

이 문제는 Dynamic Programming(DP)을 활용하여 해결할 수 있다. 각 상태를 정의하고, 그 상태에서의 최소 거리를 구하는 방식으로 접근한다.

  1. 상태 정의:
    • DP 배열 dp[i][j]를 정의한다. 여기서 i는 경찰차 1이 마지막으로 처리한 사건의 번호, j는 경찰차 2가 마지막으로 처리한 사건의 번호를 의미한다.
    • dp[i][j]는 경찰차 1이 사건 i까지, 경찰차 2가 사건 j까지 처리했을 때의 최소 이동 거리의 합이다.
  2. 초기화:
    • dp[0][0] = 0으로 초기화한다. 아직 아무 사건도 처리하지 않은 상태이다.
  3. 상태 전이:
    • 다음 처리해야 할 사건의 번호는 next = max(i, j) + 1이다.
    • 경찰차 1이 다음 사건 next를 처리하는 경우:
      • 이전 위치에서 다음 사건 위치까지의 거리를 계산하고, dp[next][j]를 갱신한다.
    • 경찰차 2가 다음 사건 next를 처리하는 경우:
      • 마찬가지로 dp[i][next]를 갱신한다.
  4. 최소값 선택:
    • 모든 가능한 i, j에 대해 DP를 수행하고, 마지막에 dp[W][j] 또는 dp[i][W] 중 최소값을 선택한다.
  5. 경로 추적:
    • 부모 상태를 저장하여 어떤 경찰차가 어떤 사건을 처리했는지 추적한다.

이러한 방식으로 DP를 수행하면 시간 복잡도는 O(W^2)로, W가 최대 1,000이므로 제한 시간 내에 해결할 수 있다.

C++ 코드와 설명

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <climits>

using namespace std;

const int MAX_W = 1001;
const int INF = INT_MAX;

int N, W;
pair<int, int> events[MAX_W]; // 사건들의 위치를 저장
int dp[MAX_W][MAX_W]; // DP 테이블
int path[MAX_W][MAX_W]; // 경로 추적을 위한 테이블

// 두 지점 사이의 거리를 계산하는 함수
int distance(const pair<int, int>& a, const pair<int, int>& b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

// DP 함수 선언
int solve(int car1, int car2);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> W;
    for (int i = 1; i <= W; ++i) {
        cin >> events[i].first >> events[i].second;
    }

    memset(dp, -1, sizeof(dp));

    cout << solve(0, 0) << '\n';

    int car1 = 0, car2 = 0;
    for (int i = 1; i <= W; ++i) {
        int next = path[car1][car2];
        cout << next << '\n';
        if (next == 1) {
            car1 = i;
        } else {
            car2 = i;
        }
    }

    return 0;
}

// DP 함수 구현
int solve(int car1, int car2) {
    int next = max(car1, car2) + 1;
    if (next > W) return 0;
    if (dp[car1][car2] != -1) return dp[car1][car2];

    // 경찰차 1이 사건 처리하는 경우
    int dist1;
    if (car1 == 0) {
        dist1 = distance({1, 1}, events[next]);
    } else {
        dist1 = distance(events[car1], events[next]);
    }
    int cost1 = solve(next, car2) + dist1;

    // 경찰차 2가 사건 처리하는 경우
    int dist2;
    if (car2 == 0) {
        dist2 = distance({N, N}, events[next]);
    } else {
        dist2 = distance(events[car2], events[next]);
    }
    int cost2 = solve(car1, next) + dist2;

    // 최소값 선택 및 경로 저장
    if (cost1 < cost2) {
        dp[car1][car2] = cost1;
        path[car1][car2] = 1;
    } else {
        dp[car1][car2] = cost2;
        path[car1][car2] = 2;
    }

    return dp[car1][car2];
}

코드 설명

  • 입력 부분:
    • 도시 크기 N과 사건의 수 W를 입력받는다.
    • 각 사건의 위치를 events 배열에 저장한다.
  • DP 초기화:
    • dp 배열을 -1로 초기화하여 메모이제이션에 활용한다.
  • solve 함수:
    • 재귀적으로 DP를 수행한다.
    • car1, car2는 각각 경찰차 1과 2가 마지막으로 처리한 사건 번호이다.
    • next는 다음에 처리해야 할 사건 번호이다.
    • 종료 조건은 next > W인 경우로, 모든 사건을 처리한 상태이다.
  • 거리 계산:
    • 경찰차의 현재 위치에서 다음 사건 위치까지의 거리를 계산한다.
    • 초기 위치는 각각 (1, 1)과 (N, N)이다.
  • 경로 추적:
    • path 배열에 어떤 경찰차가 해당 상태에서 선택되었는지 저장한다.
    • 이를 통해 나중에 어떤 경찰차가 어떤 사건을 처리했는지 알 수 있다.
  • 메인 함수:
    • solve(0, 0)을 호출하여 DP를 시작한다.
    • 이후 path 배열을 이용하여 각 사건마다 어느 경찰차가 처리했는지 출력한다.

C++ without library 코드와 설명

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#include <stdio.h>
#include <stdlib.h>

#define MAX_W 1001
#define INF 1000000000

int N, W;
int events[MAX_W][2]; // 사건들의 위치를 저장
int dp[MAX_W][MAX_W]; // DP 테이블
int path[MAX_W][MAX_W]; // 경로 추적을 위한 테이블

// 절댓값 함수 구현
int abs(int x) {
    return x < 0 ? -x : x;
}

// 두 지점 사이의 거리를 계산하는 함수
int distance(int a_x, int a_y, int b_x, int b_y) {
    return abs(a_x - b_x) + abs(a_y - b_y);
}

// DP 함수 선언
int solve(int car1, int car2);

int main() {
    scanf("%d %d", &N, &W);
    for (int i = 1; i <= W; ++i) {
        scanf("%d %d", &events[i][0], &events[i][1]);
    }

    for (int i = 0; i <= W; ++i)
        for (int j = 0; j <= W; ++j)
            dp[i][j] = -1;

    printf("%d\n", solve(0, 0));

    int car1 = 0, car2 = 0;
    for (int i = 1; i <= W; ++i) {
        int next = path[car1][car2];
        printf("%d\n", next);
        if (next == 1) {
            car1 = i;
        } else {
            car2 = i;
        }
    }

    return 0;
}

// DP 함수 구현
int solve(int car1, int car2) {
    int next = (car1 > car2 ? car1 : car2) + 1;
    if (next > W) return 0;
    if (dp[car1][car2] != -1) return dp[car1][car2];

    // 경찰차 1이 사건 처리하는 경우
    int dist1;
    if (car1 == 0) {
        dist1 = distance(1, 1, events[next][0], events[next][1]);
    } else {
        dist1 = distance(events[car1][0], events[car1][1], events[next][0], events[next][1]);
    }
    int cost1 = solve(next, car2) + dist1;

    // 경찰차 2가 사건 처리하는 경우
    int dist2;
    if (car2 == 0) {
        dist2 = distance(N, N, events[next][0], events[next][1]);
    } else {
        dist2 = distance(events[car2][0], events[car2][1], events[next][0], events[next][1]);
    }
    int cost2 = solve(car1, next) + dist2;

    // 최소값 선택 및 경로 저장
    if (cost1 < cost2) {
        dp[car1][car2] = cost1;
        path[car1][car2] = 1;
    } else {
        dp[car1][car2] = cost2;
        path[car1][car2] = 2;
    }

    return dp[car1][car2];
}

코드 설명

  • stdio.h와 stdlib.h만을 사용하여 구현하였다.
  • C 스타일의 배열과 함수만을 사용하여 이전 코드와 동일한 로직을 구현하였다.
  • abs 함수를 직접 구현하여 사용하였다.
  • 나머지 로직은 이전 C++ 코드와 동일하다.

Python 코드와 설명

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

import sys
sys.setrecursionlimit(1000000)

N = int(sys.stdin.readline())
W = int(sys.stdin.readline())
events = [None] * (W + 1)
for i in range(1, W + 1):
    x, y = map(int, sys.stdin.readline().split())
    events[i] = (x, y)

dp = [[-1] * (W + 1) for _ in range(W + 1)]
path = [[0] * (W + 1) for _ in range(W + 1)]

def distance(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def solve(car1, car2):
    next_event = max(car1, car2) + 1
    if next_event > W:
        return 0
    if dp[car1][car2] != -1:
        return dp[car1][car2]

    # 경찰차 1이 사건 처리하는 경우
    if car1 == 0:
        dist1 = distance((1, 1), events[next_event])
    else:
        dist1 = distance(events[car1], events[next_event])
    cost1 = solve(next_event, car2) + dist1

    # 경찰차 2가 사건 처리하는 경우
    if car2 == 0:
        dist2 = distance((N, N), events[next_event])
    else:
        dist2 = distance(events[car2], events[next_event])
    cost2 = solve(car1, next_event) + dist2

    if cost1 < cost2:
        dp[car1][car2] = cost1
        path[car1][car2] = 1
    else:
        dp[car1][car2] = cost2
        path[car1][car2] = 2

    return dp[car1][car2]

print(solve(0, 0))

car1, car2 = 0, 0
for _ in range(W):
    next_move = path[car1][car2]
    print(next_move)
    if next_move == 1:
        car1 = max(car1, car2) + 1
    else:
        car2 = max(car1, car2) + 1

코드 설명

  • 입력 부분:
    • 도시 크기 N과 사건의 수 W를 입력받는다.
    • 각 사건의 위치를 events 리스트에 저장한다.
  • DP 테이블 초기화:
    • dp와 path를 2차원 리스트로 초기화한다.
  • distance 함수:
    • 두 지점 사이의 거리를 계산한다.
  • solve 함수:
    • 재귀적으로 DP를 수행한다.
    • 메모이제이션을 위해 dp 테이블을 활용한다.
  • 결과 출력:
    • solve(0, 0)의 결과를 출력한다.
    • path 테이블을 이용하여 각 사건마다 어느 경찰차가 처리했는지 출력한다.

결론

이 문제는 Dynamic Programming의 대표적인 예제로, 상태 정의와 메모이제이션을 통한 최적화가 중요하다. 각 상태에서의 최적해를 구하고, 이를 기반으로 전체 문제의 최적해를 도출하는 과정이 핵심이다.

문제를 풀면서 DP의 상태 설계와 재귀 함수의 작성 방법에 대해 다시 한 번 생각해볼 수 있었다. 또한, 메모이제이션을 통해 중복 계산을 방지함으로써 시간 복잡도를 효과적으로 줄일 수 있었다.

추가적인 최적화로는 DP 테이블의 크기를 줄이거나, 반복문을 활용하여 Bottom-Up 방식으로 구현하는 방법이 있다. 그러나 이 문제에서는 재귀와 메모이제이션을 통한 Top-Down 방식이 이해하기 쉽고 구현도 간단하다.

이번 문제를 통해 DP의 중요성과 활용 방법에 대해 다시 한 번 깨달을 수 있었다. 앞으로도 다양한 문제에 DP를 적용하여 최적해를 구하는 연습을 지속해야겠다.

Tags: , , , , , , ,

Categories:

Source File: 2024-09-23-BOJ-2618.md

Updated:

Comments

You May Also Enjoy

[Algorithm] C++/Python 백준 5670번 : 휴대폰 자판

8 minute read

휴대폰에서 영단어를 입력할 때 버튼을 누르는 횟수를 최소화하기 위해 자동완성 기능을 활용하는 문제이다. 이 문제는 Trie(트라이) 자료 구조 또는 재귀적인 접근 방식을 사용하여 효율적으로 해결할 수 있다.

[Algorithm] C++/Python 백준 3679번 : 단순 다각형

6 minute read

이번 글에서는 주어진 점들로 자기 교차 없이 단순 다각형을 구성하는 문제인 백준 3679번 “단순 다각형”을 소개하고, 이를 해결하기 위한 접근 방식과 구현 방법을 살펴보겠다. 이 문제는 기하학적 알고리즘과 정렬을 활용하여 해결할 수 있으며, 효율적인 구현이 요구된다.

[Algorithm] C++/Python 백준 3653번 : 영화 수집

3 minute read

상근이는 영화 DVD를 수집하는 열성적인 수집가이다. 그는 자신의 DVD 콜렉션을 탑처럼 쌓아 보관한다. 영화를 보고 싶을 때마다 DVD의 위치를 찾아서, 쌓여 있는 콜렉션이 무너지지 않도록 조심스럽게 해당 DVD를 꺼낸다. 영화를 다 본 후에는 그 DVD를 가장 위에 놓는다.

[Algorithm] C++/Python 백준 3176번 : 도로 네트워크

5 minute read

N개의 도시와 그 도시들을 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시는 유일한 경로로 연결되어 있으며, 각 도로의 길이는 입력으로 주어진다.