백준 2795: 사업 확장

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

 

이 문제를 풀었을 때엔 조금 당황스러웠다. 독특한 아이디어라서 플레는 받을 줄 알았는데, 지금까지 푼 문제중 최고 난이도인 다이아 3이라서, 난이도가 공개되었을 때엔 내 머릿속에 물음표가 가득했었다. 내가 이전에 풀었던 다른 다이아 혹은 플레 상위 문제들이 내 머릿속을 지나갔었지만, 그래도 난이도 높은 문제를 구글링 없이 시간 내에 풀어서 속 시원하니 넘어가자.

 

이 문제의 주목해야하는 점은 두가지다.

첫째, 양방향이 아니다. 그래서 다익스트라로 출발지와 목적지간의 최소 거리를 구해서 이 경로로 왕복하는 것이 답이 아니다.

둘째, N은 100이하이고, 몇 번을 방문해도 값을 부과하지 않는다. 그렇기에 이 문제는 목적지에서 출발지까지의 경로를 저장하고, 다시 출발지로 돌아가는 과정에서 기존에 방문한 도시에선 요금을 부가하지 않도록 해야한다. 그런데, 다익스트라를 사용할 때엔 이것을 비트마스크를 사용해서 경로를 저장하는데(DP[현재 위치][지나온 경로]), 메모리 제한이 int형 100 * 2¹⁰⁰ 을 넘어가는 문제는 없다.

 

그럼 여기서 출발지에서 목적지까지의 경로를 어떻게 저장할지가 문제가 된다. 비트마스크는 절대 사용할 수 없다. 그러면 백트래킹을 사용하면 어떨까? 마침 N과 M이 비교적 작고, 답이 존재하는 경우만 입력으로 주어진다고 하니, 사용해볼 가치가 있을것 같다.

 

처음에는 백트래킹으로 출발지와 목적지간의 경로와, 출발지로 되돌아가는 경로 이 두가지를 구한 뒤, 합쳐서 중복을 제하면 그것이 답이다!라 생각했다. 이것을 위해 Set을 사용해 중복을 제거하자는 생각까지 했었는데, 이 방식은 시간 초과 혹은 메모리 초과가 될 것 같은 예감이 들어서, 다른 방식을 생각했다.

 

출발지와 목적지간의 경로를 백트래킹으로 구하는 것까지는 같지만, 다시 되돌아올때는 다익스트라를 사용하는 아이디어가 떠올랐다. 이 때, 기존의 지나온 도시인 경우, 값을 부과하지 않는다. 이 방식도 시간 초과의 우려가 있었지만, 혹시나 해서 구현을 하였다.

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
int N, M, A, B, D[101], ans = 1000000007;
vector<int> route, adj[101];
bool c[101], v[101];
void solve()
{
	for (int i = 0; i < route.size(); i++) c[route[i]] = true;
	for (int i = 1; i <= N; i++) D[i] = 1000000007;
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, 2 });
	D[2] = 0;
	while (!pq.empty())
	{
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		for (int there : adj[here])
		{
			int nxtCost = cost + !(c[there]);
			if (D[there] <= nxtCost) continue;
			D[there] = nxtCost;
			pq.push({ -nxtCost, there });
		}
	}
	for (int i = 0; i < route.size(); i++) c[route[i]] = false;
	ans = min(ans, (int)route.size() + D[1]);
}
void dfs(int here)
{
	if (here == 2) solve();
	for (int there : adj[here])
	{
		if (v[there]) continue;
		v[there] = true;
		route.push_back(there);
		dfs(there);
		v[there] = false;
		route.pop_back();
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> A >> B;
		adj[A].push_back(B);
	}
	route.push_back(1);
	v[1] = true;
	dfs(1);
	cout << ans << '\n';
}

결과는 역시나 "시간초과"였다. 하지만, 기존의 다른 문제에서 내가 겪은 시간초과는 1%에서 안 올라가는데, 이 문제는 32%까지 올라갔다가 "시간초과"가 표시되었다. 그렇다면, 가지치기를 하면 통과가 되지 않을까?

그렇게 나온 코드가

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
int N, M, A, B, D[101], ans = 1000000007;
vector<int> route, adj[101];
bool c[101], v[101];
void solve()
{
	for (int i = 0; i < route.size(); i++) c[route[i]] = true;
	for (int i = 1; i <= N; i++) D[i] = 1000000007;
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, 2 });
	D[2] = 0;
	while (!pq.empty())
	{
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		if (here == 1) break;
		if ((int)route.size() + cost >= ans) break; // 현재 값이 기존 정답보다 작아질 수 없으면 나온다.
		for (int there : adj[here])
		{
			int nxtCost = cost + !(c[there]);
			if (D[there] <= nxtCost) continue;
			D[there] = nxtCost;
			pq.push({ -nxtCost, there });
		}
	}
	for (int i = 0; i < route.size(); i++) c[route[i]] = false;
	ans = min(ans, (int)route.size() + D[1]);
}
void dfs(int here)
{
	if (ans <= route.size()) return; // 현재 답이 현재의 경로보다 작거나 같으면 나온다
	if (here == 2)
	{
		solve();
		return; // 목적지에 도착하면 바로 나온다.
	}
	for (int there : adj[here])
	{
		if (v[there]) continue;
		v[there] = true;
		route.push_back(there);
		dfs(there);
		v[there] = false;
		route.pop_back();
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> A >> B;
		adj[A].push_back(B);
	}
	route.push_back(1);
	v[1] = true;
	dfs(1);
	cout << ans << '\n';
}

코드를 고치는 과정 중에 이 아이디어가 아닌지 불안했었지만, 다행히 정답이라서 속이 시원하다.