문제
https://www.acmicpc.net/problem/2098
풀이
이 문제는 저번 컨닝의 기술 문제 풀었던 비트 마스킹을 이용해서 푼다길래 그걸 기반으로 접근했다. 처음에는 그래프나 다익스트라로 접근할 수 있지 않을까 생각을 했는데 좀 생각해보니 안되는 것 같아서 dp로 접근했다. 처음에는 간 횟수를 dp에 저장해서 dp /[횟수]/[지금 까지 방문한 도시 비트로 표현한 숫자]로 하고 여기서 최소 값, 현재 도시, 시작 도시를 저장했는데 이건 그냥 무지성으로 저번 문제 그대로 하면 풀릴 줄 알아서 이렇게 시도 했는데 곰곰히 생각하니까 횟수는 필요없고 지금까지 방문한 도시(다음 도시에 방문하지 말아야 할 곳을 알 수 있음)와 현재 도시(그 다음 도시로 가는 길이 있는지 확인용) 만 저장하면 돼서 dp를 /[현재 도시]/[지금까지 방문한 도시 비트로 표현한 숫자]로 바꿔서 풀었다. 다만 이렇게 하니까 그냥 반복문을 사용하면 안되고 큐를 사용해야 해서 처음에 첫 도시에 도착한 것을 기점으로 초기화해주고 그 값을 큐에 넣고 큐의 맨 앞을 꺼내서 다른 도시에 방문하고 다시 큐에 다시 넣고 이런식으로 문제를 풀었다.
다만 이렇게 푸니까 시간도 남들에 비해 많이 나오고 메모리도 많이 먹길래 다른 사람은 어떻게 푸나 봤다. 보니까 나랑 효율이 엄청나게 차이나더라. 먼저 다른 사람들은 내 코드에 두가지를 더 고려하여 풀었는데
- 어차피 우리가 원하는 것은 cycle이기 때문에 어느 정점에서 시작하나 결과(비용)은 같다는 것
- 중간에 중복되는 경로가 존재하고 이 중복되는 경로의 최소 또한 구해서 memoization할 수 있다는 것
여기서 기본기 차이가 많이 나는 것을 느꼈다. 이제 슬슬 종만북을 봐야할 시점이 아닌가 생각이 든다.
이거 다른 사람 푼거보니까. pow 연산만 비트로 바꾸면 정상 시간이 나올것 같아.
걸린 시간 : 1시간 31분 45초
실수
- 처음에 점화식 생각을 잘못해서 시간이 오래 걸림
- 시작하는 정점이 어디든 상관없다는 것을 깨닫지 못함
- dp의 최적 부분구조를 고려하지 않고 푸는 것 같음.
코드
- 은 그대로 고쳤는데 2.는 고치지 않았다. 그래서 시간이 400ms...
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <utility>
#include <queue>
using namespace std;
vector<vector<pair<int, int>>> dp(20, vector<pair<int, int>>(100000, make_pair(1e9, 0)));
vector<vector<int>> cost(20, vector<int>(20, 0));
queue<pair<int, int>> q;
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &cost[i][j]);
}
}
int i = 0;
dp[i][pow(2, i)].first = 0;
dp[i][pow(2, i)].second = i;
q.push(make_pair(i, pow(2, i)));
while (!q.empty()) {
pair<int, int> temp = q.front();
q.pop();
for (int i = 0; i < n; i++) {
if (((temp.second >> i) & 1) == 0 && cost[temp.first][i] != 0
&& dp[i][temp.second + pow(2, i)].first > dp[temp.first][temp.second].first + cost[temp.first][i]) {
dp[i][temp.second + pow(2, i)].first = dp[temp.first][temp.second].first + cost[temp.first][i];
dp[i][temp.second + pow(2, i)].second = dp[temp.first][temp.second].second;
q.push(make_pair(i, temp.second + pow(2, i)));
}
}
}
int res = 1e9;
for (int i = 0; i < n; i++) {
if (dp[i][pow(2, n) - 1].second < n && cost[i][dp[i][pow(2, n) - 1].second] != 0) {
res = min(res, dp[i][pow(2, n) - 1].first + cost[i][dp[i][pow(2, n) - 1].second]);
}
}
printf("%d", res);
return 0;
}