# 2098. 외판원 순회 [링크](https://www.acmicpc.net/problem/2098) | 난이도 | 정답률(\_%) | | :----: | :---------: | |Gold I|26.492| ## 설계 ### 동적계획법 ## 정리 | 내 코드 (ms) | 빠른 코드 (ms) | | :----------: | :------------: | |24| | ## 고생한 점 ## 코드 ```cpp #include <algorithm> #include <iostream> #include <string> #include <vector> #include <cstring> #include <limits> #define SIZE 16 + 1 #define INF 1000000000 using namespace std; int N; int graph[SIZE][SIZE]; int dp[SIZE][1 << 16]; int tsp(int curr, int visited) { //현재 몇번 째 마을에 위치하는지, 어느 마을을 방문하고 왔는지 int ret = dp[curr][visited]; if (dp[curr][visited] != 0) //이미 구한 적 있다면 return dp[curr][visited]; if (visited == (1 << N) - 1) { //모든 마을 방문했을 때 if (graph[curr][0] != 0) { //0번 마을로 갈 수 있을 때 return graph[curr][0]; } return INF; //불가능 하도록 매우 큰 수를 return } dp[curr][visited] = INF; for (int i = 0; i<N; i++) { if ((visited & 1 << i) || (graph[curr][i] == 0)) //i번째 visited 를 확인하기 위한 bit 연산 continue; dp[curr][visited] = min(dp[curr][visited], tsp(i, (visited | 1 << i)) + graph[curr][i]); } return dp[curr][visited]; } void solution() { cin >> N; for (int from = 0; from < N; from++) { for (int to = 0; to < N; to++) { cin >> graph[from][to]; } } int answer = tsp(0, 1); cout << answer << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solution(); return 0; } ```
Activity