boj 2098 외판원 순회

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

2098번: 외판원 순회

풀 수 있었는데 결국에는 못풀었다. 흑흑

다 왔는데 또또또또또또 문제를 완벽히 읽지 않아서 질문게시판의 TC를 참고해 버렸다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define pii pair<int, int>
#define FULL 65536
#define INF 987654321
using namespace std;
 
int d[16][FULL];
int arr[16][16];
int n;
//visit이 0이면 방문, 1이면 방문 X
int    go(int cur, int visit)
{
    if (visit == (1 << n) - 1)
        return d[cur][visit] = arr[cur][0];
 
    if (d[cur][visit] != INF)
        return d[cur][visit];
 
 
    for (int i = 0; i < n; i++)
    {
        if (((visit & 1 << i) != 0) || cur == i)
            continue;
        
        int n_visit = visit + (1 << i);
        d[cur][visit] = min(d[cur][visit], arr[cur][i] + go(i, n_visit));
    }
 
    return d[cur][visit];
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cin >> arr[i][j];
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < (1<<n); j++)
            d[i][j] = INF;
    }
 
    cout << go(0, 1);
    /*
    cout << "???? "<< go(0, 1) << '\n';
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < (1 << n); j++)
            cout << d[i][j] << ' ';
        cout << '\n';
    }
    */
 
}

이것이 직전의 소스인데

문제 지문 중에 -> 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

라는것을 파악하지 못했다. 그래서 그것을 수정하니 정답이 나왔다. 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define pii pair<int, int>
#define FULL 65536
#define INF 987654321
using namespace std;
 
 
int d[16][FULL];
int arr[16][16];
int n;
//visit이 0이면 방문, 1이면 방문 X
int    go(int cur, int visit)
{
    if (visit == (1 << n) - 1)
    {
        if(arr[cur][0] != 0)
            return d[cur][visit] = arr[cur][0];
    }
 
    if (d[cur][visit] != INF)
        return d[cur][visit];
 
 
    for (int i = 0; i < n; i++)
    {
    
        if (((visit & 1 << i) != 0) || cur == i || arr[cur][i] == 0)
            continue;
 
        int n_visit = visit + (1 << i);
        d[cur][visit] = min(d[cur][visit], arr[cur][i] + go(i, n_visit));
    }
 
    return d[cur][visit];
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cin >> arr[i][j];
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < (1<<n); j++)
            d[i][j] = INF;
    }
    
    cout << go(0, 1);
    /*
    cout << "???? "<< go(0, 1) << '\n';
 
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < (1 << n); j++)
            cout << d[i][j] << ' ';
        cout << '\n';
    }
    */
 
}