[백준 문제 C++] 2618 경찰차

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

2618번: 경찰차

 

dp에 어떻게 저장해야 될까? 생각이 안나서

구글링으로.. 다른 사람의 코드를 참고했고 이제 좀 이해가 되었다. (나중에 까먹을까봐 적어둔다 ㅠ)

 

사건을 중심으로 전개를 해야되는 방법이다.

최대 1000 * 1000 의 상태로 문제를 바꿔서 바라보는 방법이 필요했다. (이게 어려움..)

 

[ 1번 경찰차 최근 해결 사건 번호 ] [ 2번 경찰차 최근 해결 사건 번호 ]

 

DFS를 통해 사건 담당 상태에 따라 값을 갱신시켜준다.

겹치는 부분은 dp 값을 이용하여 대체가 가능해진다.

 

아래는 사건이 4개인 경우 DFS를 진행한 결과이다.

크기가 크지 않아 겹치는 주황 부분이 많지 않지만 사건의 갯수가 많아지면

생략되는 탐색이 많아지기에 효과를 볼 수 있다.

 

FindMinPath 가 깊이 우선 탐색을 하며 dp를 갱신하는 핵심 함수이고,

ShowPath에선 p1, p2의 현재 위치에서 탐색 비용과 이미 dp에 저장된 결과값의 최소값을

따라가며 경로를 알 수 있게 된다.

ex) (p1 : 경찰차1 , p2 : 경찰차2)

[p1][p2] 에 대한 최적의 루트는 이미 FindMinPath를 통해 갱신되었기에

경찰차1 목적지의 비용 + dp[목적지][p2]

경찰차2 목적지의 비용 + dp[p1][목적지]

중 어디가 더 비용이 적은지 탐색하며 p1과 p2를 바꿔주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct Position
{
	int x, y;
}Position;

vector<Position> pos;
int dp[1002][1002];
int n, w;

int GetDistance(Position pos1, Position pos2)
{
	return abs(pos1.x - pos2.x) + abs(pos1.y - pos2.y);
}

int FindMinPath(int p1, int p2, int next)
{
	if (next > w) //사건의 수가 w개를 넘으면 종료합니다.
	{
		return 0;
	}

	if (dp[p1][p2] != 0)
	{
		return dp[p1][p2];
	}
        //GetDistance를 통해 해밍턴 거리를 구하고 DFS 탐색을 이어나갑니다.
	int p1Cost = GetDistance(pos[p1], pos[next]) + FindMinPath(next, p2, next + 1);
	int p2Cost = GetDistance(pos[p2], pos[next]) + FindMinPath(p1, next, next + 1);

	return dp[p1][p2] = min(p1Cost, p2Cost);
}

void ShowPath(int p1, int p2)
{
        //dp를 통해 경로를 역추적합니다.
	for (int next = 1; next <= w; ++next)
	{
		int p1Cost = GetDistance(pos[p1], pos[next]) + dp[next][p2];
		int p2Cost = GetDistance(pos[p2], pos[next]) + dp[p1][next];

		if (p1Cost < p2Cost)
		{
			cout << 1 << endl;
			p1 = next;
		}
		else
		{
			cout << 2 << endl;
			p2 = next;
		}
	}
}

int main()
{
	cin.tie(0);
	cin >> n >> w;

        //편의를 위해 미리 경찰차1, 경찰차2 위치를 저장해줍니다.
	pos.resize(w + 2);
	pos[0] = Position{ 1, 1 };     //0 을 경찰차1 위치로 정해줍니다.
	pos[w + 1] = Position{ n, n }; //w + 1 을 경찰차2 위치로 정해줍니다.

	for (int i = 1; i <= w; ++i) //1 ~ w 까지만 입력을 받습니다.
	{
		cin >> pos[i].x >> pos[i].y;
	}

        //첫번째 경찰차 인덱스[0], 두번째 경찰차[w + 1], 첫 사건 번호[1]
	int cost = FindMinPath(0, w + 1, 1);
	cout << cost << endl;
        //첫번째 경찰차는 0, 두번째 경찰차는 w + 1
	ShowPath(0, w + 1);
}