경찰차들은 도시의 여러 사건을 처리하기 위해 최적의 경로를 찾아야 한다. 이때 두 대의 경찰차가 이동한 거리의 합을 최소화하는 것이 목표이다. 도시의 구조와 사건의 발생 위치가 주어졌을 때, 어떻게 하면 두 경찰차의 총 이동 거리를 최소화할 수 있을까?
문제 : https://www.acmicpc.net/problem/2618
문제 설명
도시는 N x N 크기의 격자 형태로 이루어져 있으며, 각 도로는 동서방향과 남북방향으로 구분된다. 동서방향 도로는 위에서부터 1부터 N까지 번호가 매겨지고, 남북방향 도로는 왼쪽에서부터 1부터 N까지 번호가 매겨진다. 도로들이 교차하는 지점은 (동서방향 도로 번호, 남북방향 도로 번호)로 표시된다.
두 대의 경찰차가 있으며, 경찰차 1은 (1, 1) 위치에서, 경찰차 2는 (N, N) 위치에서 출발한다. W개의 사건이 발생하며, 각 사건은 특정 위치에서 발생한다. 각 사건은 두 경찰차 중 하나가 처리해야 하며, 사건은 발생한 순서대로 처리해야 한다.
목표는 두 경찰차가 이동한 거리의 합을 최소화하면서 모든 사건을 처리하는 것이다. 사건을 어떤 경찰차가 처리할지 결정하고, 최소 이동 거리를 구하는 프로그램을 작성해야 한다.
접근 방식
이 문제는 Dynamic Programming(DP)을 활용하여 해결할 수 있다. 각 상태를 정의하고, 그 상태에서의 최소 거리를 구하는 방식으로 접근한다.
상태 정의:
- DP 배열
dp[i][j]를 정의한다. 여기서 i는 경찰차 1이 마지막으로 처리한 사건의 번호, j는 경찰차 2가 마지막으로 처리한 사건의 번호를 의미한다. dp[i][j]는 경찰차 1이 사건 i까지, 경찰차 2가 사건 j까지 처리했을 때의 최소 이동 거리의 합이다.
초기화:
dp[0][0] = 0으로 초기화한다. 아직 아무 사건도 처리하지 않은 상태이다.
상태 전이:
- 다음 처리해야 할 사건의 번호는
next = max(i, j) + 1이다. - 경찰차 1이 다음 사건
next를 처리하는 경우:- 이전 위치에서 다음 사건 위치까지의 거리를 계산하고,
dp[next][j]를 갱신한다.
- 경찰차 2가 다음 사건
next를 처리하는 경우:
최소값 선택:
- 모든 가능한
i, j에 대해 DP를 수행하고, 마지막에 dp[W][j] 또는 dp[i][W] 중 최소값을 선택한다.
경로 추적:
- 부모 상태를 저장하여 어떤 경찰차가 어떤 사건을 처리했는지 추적한다.
이러한 방식으로 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를 적용하여 최적해를 구하는 연습을 지속해야겠다.
![Featured image of post [Algorithm] C++/Python 백준 2618번 : 경찰차](/post/algorithm/2024-09-23-boj-2618/tmp_wordcloud_hu15466811294585815865.png)
