외판원 순회 문제에 사소한 추가 요소가 있는 문제이다. 첫 시도부터 이것이 외판원 순회 문제라고는 생각하지 못했으나 다 풀고 보니 그 문제였다. 문제의 조건을 천천히 음미해 보자.
- 그림을 팔 때, 그림을 산 가격보다 크거나 같은 가격으로 팔아야 한다.
- 같은 그림을 두 번 이상 사는 것은 불가능하다.
기본적으로 이 문제에서 주어지는 그래프는 모든 노드가 자기 자신을 제외한 모든 노드에게 향하는 간선을 갖고 있는 완전 그래프이자, 양방향의 가중치가 다른 유향 그래프이다. 하지만 1번 조건에 의해 이러한 간선들 중에서도 현재까지의 최대 판매가 이상의 가중치를 가진 간선만 확장할 수 있다는 제약이 생기고, 2번 조건에 의해 한 번 방문한 노드는 다시 방문할 수 없다는 제약이 생긴다.
1. 백트래킹 접근
일단 이 문제를 보고 처음엔 백트래킹 접근을 떠올렸다.
#include <bits/stdc++.h>
using namespace std;
int N, maxCount;
vector<vector<int>> graph;
vector<bool> visited;
void dfs(int depth, int prev, int maxPrice);
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
graph.resize(N, vector<int>(N));
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++) {
char input;
cin >> input;
graph[r][c] = input - '0';
}
visited.resize(N, false);
visited[0] = true;
dfs(1, 0, 0);
cout << maxCount;
return 0;
}
void dfs(int depth, int prev, int maxPrice) {
if (depth == N) {
cout << N;
exit(0);
}
bool isExpanded = false;
for (int i = 1; i < N; i++)
if (!visited[i] && graph[prev][i] >= maxPrice) {
isExpanded = true;
visited[i] = true;
dfs(depth + 1, i, graph[prev][i]);
visited[i] = false;
}
if (!isExpanded)
maxCount = max(maxCount, depth);
}일반적인 백트래킹 접근 방식으로 방문 여부를 갱신하면서 해결하고자 하니 시간 초과에 걸렸다. 일단 백트래킹으로 코드를 잘 짜두면 문제를 DP로 해결하기가 용이해지는데, 이 코드는 백트래킹 풀이만을 위해 작성된 것이므로 즉시 DP를 적용하기는 어렵다. 그래서 최적화할 만한 포인트를 찾아봤다.
일단 코드의 dfs()에서 depth 매개변수는 사용할 필요가 없다. 최초 코드를 작성할 때는 최대 깊이를 달성했을 때 즉시 종료하고자 해당 매개변수를 사용하였으나 굳이 필요한 변수는 아니다.
그리고 visited를 잘 생각해 보면, 최대 노드 개수가 15개이기 때문에 비트마스킹으로 최적화할 수 있다.
2. DP 최적화
#include <bits/stdc++.h>
using namespace std;
#define NONE 0
int N, maxCount;
vector<vector<int>> graph;
int cache[16][10][1<<16]; // [prev][maxPrice][visited mask]
int dfs(int prev, int maxPrice, int visited);
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
graph.resize(N, vector<int>(N));
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++) {
char input;
cin >> input;
graph[r][c] = input - '0';
}
cout << dfs(0, 0, 1);
return 0;
}
int dfs(int prev, int maxPrice, int visited) {
int& ret = cache[prev][maxPrice][visited];
if (ret != NONE)
return ret;
for (int i = 1; i < N; i++)
if (!(visited & (1 << i)) && graph[prev][i] >= maxPrice) {
ret = max(ret, dfs(i, graph[prev][i], visited | (1 << i)));
}
return ++ret;
}DP로 최적화한 코드이다. 이 문제는 이전에 방문한 노드, 현재까지의 최대 판매 가격, 방문된 노드들의 정보만 있으면 해를 구하기에 충분하다.
이전에 방문한 노드(prev)는 현재 어떤 노드에서 확장해야 하는지를 추적하기 위해 필요하고, 현재까지의 최대 판매 가격(maxPrice)과 방문된 노드들(visited)은 확장할 수 있는 간선을 파악하기 위해 필요하다.
해결 후 솔브닥 리뷰를 보니 캐시를 3차원 배열로 선언하는 데서 많은 사람들이 애를 먹은 듯한데, 백트래킹으로 먼저 점화식을 생각해 보고 top-down 방식으로 해결하면 그리 어려운 문제는 아닌 것 같다. 백트래킹 로직을 구성함에 있어서 중요한 것은 매개변수 최적화 외엔 없다.
