(2098) 외판원 순회

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

단계별로 풀어보기

40단계(동적 계획법 3) 3번째

 

 

 

이전 문제는 모든 사람이 모든 일을 할 수 있었지만 이 문제는 도시에 따라 다음에 갈 수 있는 도시의 범위가 달라지고 마지막에 처음 도시로 돌아와야 하는 조건도 있다. 따라서 state뿐만 아니라 현재 도시 위치도 저장해줘야 한다.

dp[x][state]: x번 도시에 있고 state상태일 때 남은 도시를 가기 위한 최소 비용

경로가 사이클을 이루므로 처음 도시에서 시작해도 문제가 없고, 마지막 state가 전부 채워졌을 때 now가 처음 도시여야 사이클이 성립하므로 아니라면 INF값을 반환하여 갱신되지 않도록 한다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define INF 200000001

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector w(n, vector<int> (n)), dp(n, vector<int> (1<<n, -1));
  
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin >> w[i][j];
    }
  }
  
  auto func= [&](auto self, int now, int state) -> int {
    if(state==(1<<n)-1)  return now==0 ? 0 : INF;
    
    int &ret= dp[now][state];
    
    if(ret!=-1)  return ret;
    
    ret= INF;
    
    for(int next=0;next<n;next++){
      if(!w[now][next])  continue;
      if(state&(1<<next))  continue;
      
      ret= min(ret, self(self, next, state|(1<<next))+w[now][next]);
    }
    
    return ret;
  };
  
  cout << func(func, 0, 0);
  
  return 0;
}