BOJ 5852 - Island Travels

BOJ 5852 - Island Travels

BFS로 섬들을 찾고, 각 섬간의 거리도 BFS로 찾은 다음에 플로이드 와샬로 모든 섬간의 거리를 구해준다.

이에 대해 외판원 순회 문제를 비트필드 DP로 풀어주는 문제이다.

이것저것 많이 쓰이는 문제이고, 기본적인 그래프에 관련된 알고리즘을 정확히 숙지하고 있다면 구현량이 좀 있을뿐 크게 아이디어 필요없이 풀 수 있다.

const int inf = 1e9;  
const int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, op[] = {2, 3, 0, 1};  
void solve() {  
   int Y, X;  
   cin >> Y >> X;  
   vs b(Y);  
   fv(b);  
   int N;  
   vector<vector<pi>> island;  
   int nxt_label = 0;  
   vvi vis(Y, vi(X)), label(Y, vi(X, -1));  
   for (int y = 0; y < Y; y++)  
      for (int x = 0; x < X; x++) {  
         if (b[y][x] == 'X' && !vis[y][x]) {  
            queue<pi> q;  
            q.push({y, x});  
            vis[y][x] = 1;  
            vector<pi> g;  
            while (sz(q)) {  
               auto[cy, cx] = q.front();  
               g.pb({cy, cx});  
               q.pop();  
               for (int d = 0; d < 4; d++) {  
                  int ny = cy + dy[d], nx = cx + dx[d];  
                  if (ny >= 0 && ny < Y && nx >= 0 && nx < X && b[ny][nx] == 'X' && !vis[ny][nx]) {  
                     vis[ny][nx] = 1;  
                     q.push({ny, nx});  
                  }  
               }  
            }  
            for (auto[y, x]: g) label[y][x] = nxt_label;  
            nxt_label++;  
            island.pb(g);  
         }  
      }  
   N = sz(island);  
   vvi d_island(N, vi(N, inf));  
   for (int i = 0; i < N; i++) {  
      for (int j = i + 1; j < N; j++) {  
         queue<pi> q;  
         int mn_dist = inf;  
         vvi dist(Y, vi(X, inf));  
         for (auto&[y, x]: island[i]) q.push({y, x}), dist[y][x] = 0;  
         while (sz(q)) {  
            auto[y, x] = q.front();  
            q.pop();  
            for (int d = 0; d < 4; d++) {  
               int ny = y + dy[d], nx = x + dx[d];  
               if (ny >= 0 && ny < Y && nx >= 0 && nx < X) {  
                  if (label[ny][nx] == j) {  
                     mn_dist = min(mn_dist, dist[y][x]);  
                  } else if (b[ny][nx] == 'S' && dist[ny][nx] > dist[y][x] + 1) {  
                     dist[ny][nx] = dist[y][x] + 1;  
                     q.push({ny, nx});  
                  }  
               }  
            }  
         }  
         d_island[i][j] = d_island[j][i] = mn_dist;  
      }  
   }  
   for (int i = 0; i < N; i++) d_island[i][i] = 0;  
   for (int c = 0; c < N; c++)  
      for (int i = 0; i < N; i++)  
         for (int j = 0; j < N; j++)  
            d_island[i][j] = min(d_island[i][j], d_island[i][c] + d_island[c][j]);  
  
   vvi dp(N, vi(1 << N, -1));  
   function<int(int, int)> fn = [&](int i, int state) -> int {  
      if (state == (1 << N) - 1) {  
         return 0;  
      }  
      int &ret = dp[i][state];  
      if (~ret) return ret;  
      ret = inf;  
  
      for (int j = 0; j < N; j++) {  
         if (!((1 << j) & state) && d_island[i][j] < inf) {  
            ret = min(ret, d_island[i][j] + fn(j, state | (1 << j)));  
         }  
      }  
  
      return ret;  
   };  
   int ans = inf;  
   for (int i = 0; i < N; i++) {  
      ans = min(ans, fn(i, 1 << i));  
   }  
   assert(ans != inf);  
   cout << ans;  
}