[ 백준 2618 ] 경찰차 (C++)

백준의 경찰차(2618) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

경찰차 2대가 주어진 사건들을 처리해야 할 때, 경찰차 2대가 움직인 거리의 합이 최소가 되는 값을 구해야 하는 문제이다.

전체적인 접근 방법부터 정답을 도출하는 과정까지 진행해보자.

 

#1. 접근방법

본인은 이 문제를 DFS + DP로 접근을 해 주었다.

재귀를 통해서 현재 사건에서 다음 사건으로 넘어갈 때, 어떤 경찰차가 가는 것이 거리상으로 더 유리한지 판단한 후에 해당 경찰차를 해당 사건 지점으로 보내는 방식으로 진행하였다.

본인은 이를 위해서 재귀함수에서 2가지 인자를 사용해 주었다.

1. 경찰차1번이 최종적으로 맡은 사건 번호

2. 경찰차2번이 최종적으로 맡은 사건 번호

위와 같이 2가지 정보를 인자로 가지고 진행해 주었다.

각 경찰차들이 맡은 사건 번호만 알고 있다면, 해당 경찰차들의 위치 또한 알 수 있고, 이 위치를 통해서 그 다음 사건까지의 거리 또한 계산을 할 수 있기 때문에 본인은 경찰차들의 좌표정보, 거리정보가 아닌 각 경찰차들이 최종적으로 맡은 사건번호만 인자로 가지고 진행해 주었다.

당연히 초기에는 최종적으로 맡은 사건이 없기 때문에 둘다 '0'으로 호출이 될 것이다.

그리고 재귀 함수가 종료되는 시점은, 2개의 경찰차 중 어느 하나라도 'W번 사건'을 맡게되는 순간 종료될 것이다.

왜냐하면, W번 사건을 최종적으로 처리하였다는 것은 더 이상 처리할 사건이 없음을 의미하기 때문에 더 이상의 탐색이 무의미하기 때문이다. 따라서, 재귀 함수의 종료 시점은 2개의 인자 중, 어느 하나라도 'W'와 같은 값을 갖는 순간 종료시켜 주었다.

즉 ! 다음과 같은 함수 안에 내용을 채워갈 것이다.

int Total_Distance(int Police1, int Police2)
{
	if (Police1 == W || Police2 == W) return 0;
}

위의 함수가 본인이 선언한 재귀함수이다. 지금부터 저 함수 안의 내용을 채워갈 것이다.

인자로 선언되어 있는 Police1은 "1번 경찰차가 최종적으로 처리한 사건 번호", Police2는 "2번 경찰차가 최종적으로 처리한 사건 번호" 를 의미한다.

 

#2. Dynamic Programming

본인은 재귀를 통해서 탐색을 하는 과정에서 DP를 사용해 주었다. 이를 이용해서 중복적으로 탐색해야 되는 경우에는 기존에 계산해놓은 결과값을 통해서 더 이상의 탐색 없이 바로 결과값을 return 시켜주는 방식으로 진행하였다.

이를 위해서 DP[][] 라는 2차원 배열을 하나 선언해 주었다.

DP[A][B] = C 의 의미는 다음과 같다.

"1번 경찰차가 A번 사건을 최종적으로 처리했고, 2번 경찰차가 B번 사건을 최종적으로 처리했을 때, 이 2대의 경찰차가 모든 사건을 처리했을 때 움직여야 하는 거리의 최소 값은 C입니다."

그리고 이 배열의 모든 값을 '-1'로 초기화를 시켜 주었다. 왜냐하면, "기존에 계산을 한 적이 있는지 없는지를 판단하기 위해서" 이다. 특정 인덱스의 값이 -1을 가지고 있다면, 이는 계산한 적이 없으니 탐색을 해봐야 하는 것이고, -1이 아닌 다른 값을 가지고 있다면 이미 계산한 적이 있으니 탐색할 필요가 없음을 의미한다.

또한 ! 거리에 음수가 발생하지 않으므로, 이미 계산한 적이 있음에도 -1이 나올 경우는 없기 때문이다.

int Total_Distance(int Police1, int Police2)
{
	if (Police1 == W || Police2 == W) return 0;
    	if (DP[Police1][Police2] != -1) return DP[Police1][Police2];
}

위와 같이 코드를 추가할 수 있다.

 

#3. 최소 거리 구하기

이제 본격적으로 위의 함수를 채워나가볼 것이다.

먼저, 거리를 구하기 위해서는 다음과 같이 2 가지 정보를 알고 있어야 한다.

1. 현재 경찰차들의 위치

2. 다음 사건이 발생하는 곳의 위치

위와 같이 2가지 정보를 알고 있어야 한다. 1번정보 같은 경우에는 #1에서 이야기 했듯이, 재귀함수의 인자로 사용되고 있는 "경찰차들이 최종적으로 처리한 사건 번호"를 통해서 경찰차들의 위치를 파악할 수 있다.

그렇다면, 다음 사건이 발생하는 곳의 위치는 어떻게 알 수 있을까 ??

예를 들어서 1번 경찰차가 최종적으로 1번 사건을 처리했고, 2번 경찰차가 최종적으로 2번 사건을 처리했다고 가정해보자.

그렇다면 다음 사건은 몇 번 사건일까 ?? 바로 '3번 사건' 일 것이다.

또 하나의 예로 1번 경찰차가 최종적으로 3번 사건을 처리했고, 2번 경찰차가 최종적으로 1번 사건을 처리했다면, 다음 사건은 몇 번 사건일까 ?? 바로 '4번 사건' 일 것이다.

즉 ! 다음 사건은 "Max(1번 경찰차가 최종적으로 처리한 사건번호 , 2번 경찰차가 최종적으로 처리한 사건번호) + 1" 이 될 것이다. 그리고 우리는 이 사건번호만 알 수 있다면, 처음 입력에서 주어진 정보를 이용해서 해당 사건이 발생하는 위치 또한 쉽게 알아낼 수 있다.

이를 바탕으로, 각 경찰차들이 다음 사건으로 가는데 까지 걸리는 거리를 다음과 같이 구할 수 있다.

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];  
}

각각의 경찰차들이 위치한 현재 지점에서 다음 사건 까지의 거리를 구하는 과정이다.

이 거리를 구한 후, line15 ~ 16)에서는 이를 바탕으로 그 다음 사건으로 넘어가는 과정까지를 구현하기 위해서 재귀를 호출하는 과정이다.

 

#4. 각 사건을 처리한 경찰차 구하기

우리는 최소 거리 뿐만 아니라 각 사건을 몇 번 경찰차들이 처리를 했는지 까지 구해야 한다.

이 과정 또한 #3에서 진행했던 과정과 매우 비슷하게 재귀를 통해서 구현하였다.

다만, 재귀 중간중간 과정에서 더 작은 값을 가지는 경찰차들을 출력해주는 과정을 추가해주었다.

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);
	}
}

 

[ 소스코드 ]

#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;
}