Gidhub BE Developer

BOJ - 외판원 순회

2018-03-27
goodGid

Problem

Problem URL : 외판원 순회

Screenshots of Problem Explain

[1] Answer Code (18. 03. 27)


#include<iostream>
#include<algorithm>
#define inf 987654321
using namespace std;

int n,all;
int cost[17][17];
int dp[17][1<<17];

int tsp(int cur, int stat){
    
    /*
     모든 정점을 다 방문했을 경우
     */
    if( stat == all )
        // 현재 cur 위치에서 돌아가야할 1위치로 가야하기 때문에
        // cost[cur][1]을 Return
        return cost[cur][1];
    
    int& ret = dp[cur][stat];
    if( ret != 0)
        return ret;
    
    ret = inf;
    for(int i=1; i<=n; i++){
        // 2개의 조건문 이해하기
        // 1. 다음 방문 위치가 방문한 상태인지 Check
        // 2. 현재위치에서 다음위치로 갈 수 있는지 Check
        if(( ( stat & ( 1 << (i-1) )) != 0 ) || cost[cur][i] == 0)
            continue;
        int value = cost[cur][i] + tsp(i, ( stat | (1 << (i-1)) ) );
        ret = min(ret, value);
    }
    return ret;
}

int main(){
    cin >> n;
    all = ( 1<< n ) - 1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            scanf("%d",&cost[i][j]);
    
    cout << tsp(1,1) << endl;
    return 0;
}


Code Review

[1] Answer Code (18. 03. 26)

  • 비트마스크를 건드렸다. 그 중 가장 유명한 TSP 문제를 풀었다.

  • 물론 답은 보고 참고하여 풀었지만 ㅎㅎ 그래도 비트를 갖고노는게 재밌네 !

  • 코드 설명은 코드에 주석으로 코멘트해놓았다.


Comments

Content