문제
풀이
DFS, DP를 이용한 최단거리 확인과 역추적 문제이다. 처음에는 그리디하게 매 경우때마다 최소 거리를 더하면 되는 코드를 작성했지만, 이는 결과적으로 전체 사건을 해결하였을 때 최소 거리라는것을 보장하지 못한다. Reference에서 코드를 가져왔다. DP[i][j]는 경찰차 1이 i번째 사건을, 경찰차 2가 j번째 사건을 해결하였을 때, 2대의 경찰차가 움직여야하는 남은 최소 거리를 의미한다. 그러므로, 원하는 결과는 DP[0][0]의 값이 되겠다. 역추적은 경찰차 1이 next_event로 갔을 때 남은 최소 이동거리와, next_event로 가는 거리의 합을 경찰차 2의 경우와 비교하여 낮은 값의 경찰차 번호를 출력해주면 된다.
소스 코드
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <cstring>
#define endl "\n"
#define MAX 1010
using namespace std;
struct COORD
{
int x;
int y;
};
int N, W;
int DP[MAX][MAX];
COORD Event[MAX];
int Max(int A, int B) { return A > B ? A : B; }
int Min(int A, int B) { return A < B ? A : B; }
void Input()
{
cin >> N >> W;
for (int i = 1; i <= W; i++)
{
cin >> Event[i].x >> Event[i].y;
}
}
int Find_Dist(int x, int y, int xx, int yy) { return abs(xx - x) + abs(yy - y); }
int Total_Distance(int Police1, int Police2)
{
if (Police1 == W || Police2 == W) return 0;
if (DP[Police1][Police2] != -1) return DP[Police1][Police2];
int Next_Event = Max(Police1, Police2) + 1;
int Dist1, Dist2;
if (Police1 == 0) Dist1 = Find_Dist(1, 1, Event[Next_Event].x, Event[Next_Event].y);
else Dist1 = Find_Dist(Event[Police1].x, Event[Police1].y, Event[Next_Event].x, Event[Next_Event].y);
if (Police2 == 0) Dist2 = Find_Dist(N, N, Event[Next_Event].x, Event[Next_Event].y);
else Dist2 = Find_Dist(Event[Police2].x, Event[Police2].y, Event[Next_Event].x, Event[Next_Event].y);
int Result1 = Dist1 + Total_Distance(Next_Event, Police2);
int Result2 = Dist2 + Total_Distance(Police1, Next_Event);
DP[Police1][Police2] = Min(Result1, Result2);
return DP[Police1][Police2];
}
void Route(int P1, int P2)
{
if (P1 == W || P2 == W) return;
int Next_Event = Max(P1, P2) + 1;
int Dist1, Dist2;
if (P1 == 0) Dist1 = Find_Dist(1, 1, Event[Next_Event].x, Event[Next_Event].y);
else Dist1 = Find_Dist(Event[P1].x, Event[P1].y, Event[Next_Event].x, Event[Next_Event].y);
if (P2 == 0) Dist2 = Find_Dist(N, N, Event[Next_Event].x, Event[Next_Event].y);
else Dist2 = Find_Dist(Event[P2].x, Event[P2].y, Event[Next_Event].x, Event[Next_Event].y);
if (DP[Next_Event][P2] + Dist1 < DP[P1][Next_Event] + Dist2)
{
cout << 1 << endl;
Route(Next_Event, P2);
}
else
{
cout << 2 << endl;
Route(P1, Next_Event);
}
}
void Solution()
{
memset(DP, -1, sizeof(DP));
cout << Total_Distance(0, 0) << endl;
Route(0, 0);
}
void Solve()
{
Input();
Solution();
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("Input.txt", "r", stdin);
Solve();
return 0;
}
//출처: https://yabmoons.tistory.com/644 [얍문's Coding World..]
실패한 코드
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
#include <iostream>
#include <vector>
using namespace std;
int N, W;
int map[1001][1001];
vector<pair<int, int>> testcase(1001);
vector<pair<pair<int, int>, pair<int, int>>> dp(1001); // i번째 사건을 해결했을 때, 경찰차 1, 2의 위치
vector<int> car;
int main(){
scanf("%d", &N);
scanf("%d", &W);
for(int i = 1; i<=W; i++){
scanf("%d %d", &testcase[i].first, &testcase[i].second); //(y, x);
}
dp[0].first.first = 1;
dp[0].first.second = 1; // 경찰차 1 초기 위치 (1,1)
dp[0].second.first = N;
dp[0].second.second = N; // 경찰차 2 초기 위치 (N,N)
//초기값 설정
int cnt = 0;
for(int i = 1; i<=W; i++){
int y_1 = abs(testcase[i].first - dp[i-1].first.first);
int x_1 = abs(testcase[i].second - dp[i-1].first.second);
// 경찰차 1의 위치와 i번째 사건과의 거리
int y_2 = abs(testcase[i].first - dp[i-1].second.first);
int x_2 = abs(testcase[i].second - dp[i-1].second.second);
// 경찰차 2의 위치와 i번째 사건과의 거리
if(y_1 + x_1 < y_2 + x_2){ // 경찰차1이 더 가깝다면...
car.push_back(1);
cnt += y_1 + x_1;
dp[i].first.first = testcase[i].first;
dp[i].first.second = testcase[i].second;
//i번째 사건을 해결했을 때, 경찰차 1의 위치는 i번째 사건의 위치
dp[i].second.first = dp[i-1].second.first;
dp[i].second.second = dp[i-1].second.second;
//경찰차 2의 위치는 그대로
}
else{
car.push_back(2);
cnt += y_2 + x_2;
dp[i].first.first = dp[i-1].first.first;
dp[i].first.second = dp[i-1].first.second;
//경찰차 1의 위치는 그대로
dp[i].second.first = testcase[i].first;
dp[i].second.second = testcase[i].second;
//i번째 사건을 해결했을 때, 경찰차 2의 위치는 i번째 사건의 위치
}
}
printf("%d\n", cnt);
for(int i = 0; i<car.size(); i++){
printf("%d\n", car[i]);
}
}
