왜판원순회

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

외판원 문제는 그래프에서 모든 정점을 방문하여 시작점으로 돌아오는 최단경로를 찾아야 하는 유명한 문제이다. 왜판원 문제의 목표는 조금 다르다. 정점의 개수가 N개인 그래프에서 역시 모든 정점을 방문하여 시작점으로 돌아오되, 정확히 그 길이가 L인 경로가 존재하는지를 알아내야 한다. 다시 말해서, 경로의 길이가 L이고 크기가 N인 싸이클이 존재하는지를 알아내야 한다.

Meet in the middle을 활용한 문제이다. 이론상으로는 구상했는데 복잡하게 생각하다보니 로직이 꼬여서 많이 고전했다.. claude와의 진지한 대화로 리팩토링해서 성공했다.

1. 특정 점이 중간에 방문하는 점이라고 가정한다.
   1. 시작 점으로부터 해당 점까지 도달하는 데 거칠 점(N/2-1)개의 점)을 마스크로 정한다.
      1. 마스크에 해당하는 점을 모두 거쳐 시작 점으로부터 해당 점까지 도달하는 경로의 길이들을 set에 저장해놓는다.
      2. 마스크를 뒤집어서, 뒤집은 마스크에 해당하는 점을 거쳐 해당 점으로부터 시작 점까지 가는 경로의 길이들을 다른 set에 저장해놓는다.
      3. 2번 단계에서 만든 set의 각 요소를 순회하며 3번 단계의 set에 (목표거리)-(한 요소)와 동일한 값을 가지는 요소가 있는지 찾는다.
   2. 가능한 모든 마스크를 순회한다.
2. 가능한 모든 중간 점을 순회한다.

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;

int n;
long long l;
vector<vector<long long> > d;

int bit_count(int msk) {
    int cnt=0;
    while (msk>0) {
        if (msk&1) cnt++;
        msk>>=1;
    }
    return cnt;
}

set<long long> f(int start, int mask, int end) {
    vector<int> x;
    set<long long> distances;
    if (mask == 0) {
        distances.insert(d[start][end]);
        return distances;
    }
    for (int i=0; i<n; i++) {
        if (mask&(1<<i)) x.push_back(i);
    }
    do {
        long long dist = d[start][x[0]];
        for (int i=0; i+1<x.size(); i++) {
            dist += d[x[i]][x[i+1]];
        }
        dist += d[x.back()][end];
        distances.insert(dist);
    } while (next_permutation(x.begin(), x.end()));
    return distances;
}

int main() {
    cin>>n>>l;
    d = vector<vector<long long> >(n, vector<long long>(n));
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            cin>>d[i][j];
        }
    }
    bool possible = false;
    for (int c=1;c<n;c++) {
        for (int mask_left=0; mask_left<(1<<n); mask_left++) {
            if (mask_left&(1<<0) || mask_left&(1<<c) || bit_count(mask_left)!=(n-2)/2) continue;
            int mask_right = (1<<n)-1 - mask_left-(1<<0)-(1<<c);

            set<long long> dl = f(0, mask_left, c);
            set<long long> dr = f(c, mask_right, 0);
            for (auto e: dl) {
                if (dr.find(l-e) != dr.end()) {
                    possible = true;
                }
            }
        }
    }
    cout<<(possible?"possible":"impossible");
    return 0;
}