반응형

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

 

2618번: 경찰차

첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄

www.acmicpc.net

 

 

[ 문제풀이 ]

 

재귀 함수와 다이나믹 프로그래밍으로 풀 수 있는 문제입니다.

 

먼저 dp[dp [ 1001 ][ 1001 ] 배열을 만듭니다. dp [ a ][ b ]에서 a는 1번 자동차의 위치, b는 2번 자동차의 위치입니다. 더 정확하게는 a번째 사건의 위치가 현재 1번 자동차의 위치, b번째 사건의 위치가 현재 2번 자동차의 위치입니다.

 

dist1은 현재 1번 자동차의 위치에서 다음 사건 위치로 옮길 때의 거리, dist2는 현재 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
#include<iostream>
#include<cmath>
 
using namespace std;
 
struct acc {        //사고의 위치 struct
    int y;
    int x;
};
 
int N, W;
 
acc arr[1001];        //사고의 위치를 저장할 배열
int dp[1001][1001];    //dp[a][b] a는 1번 자동차, b는 2번 자동차의 현재 사건 위치
 
int dist(acc a, acc b)        //a점과 b점의 거리 return
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}
 
int dfs(int a, int b)
{
    if (a == W || b == W) return 0;    //마지막 사건이라면
    if (dp[a][b] != 0) return dp[a][b];    //한번이라도 저장되었다면
 
    int nAcc = max(a, b) + 1;    //다음 사고 번호
    int dist1, dist2;
 
    if (a == 0) {        //1번 자동차가 움직였을 때의 거리
        dist1 = dist(arr[nAcc], { 1,1 });
    }
    else {
        dist1 = dist(arr[nAcc], arr[a]);
    }
    if (b == 0) {        //2번 자동차가 움직였을 때의 거리
        dist2 = dist(arr[nAcc], { N,N });
    }
    else {
        dist2 = dist(arr[nAcc], arr[b]);
    }
 
    return dp[a][b] = min(dist1 + dfs(nAcc, b), dist2 + dfs(a, nAcc));
}
 
void route(int a, int b)
{
    if (a == W || b == W) return;
 
    int nAcc = max(a, b) + 1;
    int dist1, dist2;
 
    if (a == 0) {
        dist1 = dist(arr[nAcc], { 1,1 });
    }
    else {
        dist1 = dist(arr[nAcc], arr[a]);
    }
    if (b == 0) {
        dist2 = dist(arr[nAcc], { N,N });
    }
    else {
        dist2 = dist(arr[nAcc], arr[b]);
    }
 
    if (dp[nAcc][b] + dist1 < dp[a][nAcc] + dist2) {
        printf("1\n");        //1번 자동차가 움직이는 게 가장 짧은 거리일 때
        route(nAcc, b);
    }
    else {                    //2번 자동차가 움직이는 게 가장 짧은 거리일 때
        printf("2\n");
        route(a, nAcc);
    }
 
}
 
int main()
{
    cin >> N >> W;
 
    for (int i = 1; i <= W; i++) {
        scanf("%d %d", &arr[i].y, &arr[i].x);
    }
 
    printf("%d\n", dfs(0, 0));
    route(0, 0);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2243번 - 사탕상자 (C++)  (0) 2022.07.29
[ 백준 ] 5719번 - 거의 최단 경로 (C++)  (0) 2022.07.27
[ 백준 ] 14938번 - 서강그라운드 (C++)  (0) 2022.07.25
[ 백준 ] 2150번 - Strongly Connected Component (C++)  (0) 2022.07.24
[ 백준 ] 1948번 - 임계경로 (C++)  (0) 2022.07.22

+ Recent posts

티스토리툴바