[C++] 4991 : 로봇 청소기(외판원 순회 풀이)

 

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

 

배열을 통해 적용할 수 있는 고급 테크닉들이 적용된 문제이다. 현대오토에버는 최근 AUTOSAR Classic 직무에 대해서 C 언어로만 응시할 수 있도록 프로그래밍 언어를 제한했는데, 이 경우 배열을 이용한 고난도 문제들이 등장한다. (priority queue는 구현하는데만 한 세월..이므로) 따라서 배열을 이용해서 문제를 풀어야 하는데, 그 중에서도 고급 테크닉인 DP와 비트마스킹 정도인데, 이것들이 짬뽕된 문제이다.

 

알고리즘 분류

• 다이나믹 프로그래밍
• 비트마스킹
• 외판원 순회 문제(Traveling Salesperson Problem)
• 너비 우선 탐색(BSP)

 

문제설명

 

예를 들어 이런 input이  들어오면,

7 5
.......
.o...*.
.......
.*...*.
.......

 

남쪽으로 두 칸, 동쪽으로 네 칸, 위로 2칸 가면 최단 거리 = 8로 탐색이 가능하다.

 

문제접근

이 문제는 기본적으로 모든 정점을 방문하면서 최단 거리를 구해야하는데, 핵심은 "시작점"이 매번 달라진다는 것이다. 즉 예를 들어 정점이 1, 2, 3, 4번 이 있고 1부터 시작할때, 1->2->3->4로 계산할 수도 있고, 1->3->4->2 순으로 계산할 수도 있으므로 "정점 방문 순서"가 중요해진다.

 

1. 완전 탐색으로 가능한가?

 우선 완전 탐색으로 접근해보자. 모든 경로의 순서를 구해야 하고, 따라서 총 N! 개의 경로를 일일이 비교해야 한다. 이때 n이 10이하이므로 10! 이고, 각각의 경로를 구할 때는 BFS를 이용하면 되고, 각각의 10개의 정점에 대해서 한 번만 구해놓으면 이후 계속 사용할 수 있다. 따라서 BFS는 약 10 x 20 x 20 = 4000정도 명령문이 사용되므로, 총 10! x 4000 = 4096000 이므로 1억이 되지 않는다. 따라서 이 문제는, "브루트포스" 로 풀 수 있다!

 

 

2. But... 

 브루트포스로 푸는 것은 실력 향상에 도움되지 않는다. 사실 문제가 쉽게 나온 것이다. 만약 n = 20이라면 어떨까?

20! = 20 x 19 x ... x 2 x 1 = 2,432,902,008,176,640,000

 

어마어마한 숫자다. 이는 완전탐색으로 "절대" 풀 수 없다. 만약 n = 20이라면 이 문제의 난이도는 플레티넘으로 올려야 한다. 어떻게 풀어야 할까? 바로 DP를 응용해야 한다. 이에 해당하는 문제가, 바로 외판원 순회 문제다.

외판원 순회(Traveling Salesman Problem)는 0-1 배낭 문제(Knapscak Problem)과 함께 Dynamic Programming을 적용하는 문제(그들만의 Well-known 문제..)다. 문제의 배경에 대해서는 나무위키를 참고하면 좋다.

 

https://namu.wiki/w/%EC%99%B8%ED%8C%90%EC%9B%90%20%EC%88%9C%ED%9A%8C%20%EB%AC%B8%EC%A0%9C

외판원 순회 문제

 

그럼 이 외판원 순회 문제에 대한 Dynamic Programming이 가능한지를 증명하자.

 

1. Optimal Substructure가 존재하는가?

 

우선 6개의 정점(A, B, C, D, E, F)가 있다고 가정하자.

 

그럼 현재 state를 어떻게 표현할 수 있을까? 우선 단순하게 A, B, C를 방문했다고 가정하고 그래프를 그리자. 이때 경로는 서로서로 갈 수 있다고 가정하자.

 

이 상태에서 optimal substructure로 만들 수 있는지 생각해보자. 우선 vector에 현재 방문 정점들을 담고, map 형태로 dp를 구성할 수 있을 것이다.

vector<char> v(3, 0);
v[0] = 'A'; v[1] = 'B'; v[2] = 'C';

map<int, vector<char>> dp;

 

여기서 dp의 구성은 현재 state에서 남은 정점들을 탐색하기까지의 최소 비용일 것이다. 그런데, 이걸로는 부족하다.

이렇게 현재 A에 있을때 D, E, F 까지 가는 비용과,

 

현재 B에 있을 때 D, E, F까지 가는 비용이 다르기 때문이다. 따라서, dp를 다음과 같이 세워야 한다.

{현재 위치, (현재 방문한 정점들)} -> {남은 정점을 완주하는 최소 비용}

 

여기에서 (현재 방문한 정점들)과 (남은 정점들)을 vector로 나타내지 말고, "비트마스킹"을 이용해보자. 비트마스킹..에 대해 설명하기는 어려우니 큰돌님의 블로그를 참고하면 좋겠다. 만약 비트마스킹이 어려우면 그냥 map 형태로 dp를 구현하면 된다.

https://blog.naver.com/jhc9639/222310927725

[알고리즘 강의] 4주차. 비트마스킹

 

예를 들어 A,B,C,D,E,F 정점들에 대해 현재 A,B,C 정점을 방문했다고 생각하면 bit vector는 다음과 같이 구할수 있다. 

초기 상태는 아무것도 방문 안함
	-> 000000
    
A B C 방문했다면
	-> 111000

 

따라서 현재 A 정점이고 ABC를 방문했다면 현재 bit vector에 해당하는 dp값은 다음과 같다. 

int dp[6][(1 << 6)]; // A = 5, B = 4, ... F = 0

// 현재 A 정점, A,B,C 방문상태
int now_bit_vector = to_decimal(111000);

// 현재 위치 A = 5, 현재 방문상태 bit vector = 0b111000
int now_dp = dp[5][now_bit_vector];

 

이렇게 dp 배열을 설계했다. 

 

그럼 이렇게 설계하면 시간복잡도는 어떻게 될까? 우선 bit vector의 개수는 2^n개이다. 이때 현재 위치 정점은 n개 존재하므로 State의 개수는 n * 2^n 이다. 각각의 state에 대해서 다음 갈 정점 n개를 탐색하므로 총 시간복잡도는~

O(n!) > O(2^n)이므로 훨씬 좋은 알고리즘이다.

 

2. Overlapping Subproblems는 존재하는가?

 현재 ABC방문하고 A인상태에서 나머지 경로값을 구할 때는 D->E->F 또는 E->F->D 또는 F->D->E .... 이렇게가는데 여기서 서로 겹치는 부분이 있으므로 overlapping subproblems가 존재한다.

 

정답코드

 

이를 통해 Top-Down 방식으로 DP를 이용해 외판원 순회 문제를 해결할 수 있다. 문제의 편의성을 위해 첫 시작 정점을 location[0] 에 포함시켜 bit vector를 설정했다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
void fastIO() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
}

// 시작 + 먼지의 위치 (location[0]은 시작 location[1] ~ 부터는 먼지의 위치)
pii location[11]; 

// {현재 y, 현재 x, 최대 10개의 먼지에 대한 bit_vector} -> 남은 최소 거리
int dp[11][(1 << 11)]; 

char land[24][24]; 
int dist[11][24][24]; // 시작점에 따른 최단 거리 모음
int w, h;
int dust_cnt;
const int dy[] = {0, 1, 0, -1};
const int dx[] = {1, 0, -1, 0};

bool is_out (int y, int x)
{
  return (y < 0 || y >= h || x < 0 || x >= w);
}

void bfs(int idx)
{
  int y = location[idx].first;
  int x = location[idx].second;
  queue<pii> q;
  q.push({y,x});
  dist[idx][y][x] = 0;
  
  while(q.size())
  {
    pii a = q.front(); q.pop();
    int y = a.first;
    int x = a.second;
    for (int i = 0; i < 4; i++)
    {
      int ny = y + dy[i];
      int nx = x + dx[i];
      if (is_out(ny,nx) || land[ny][nx] == 'x' || dist[idx][ny][nx] != -1) continue;
      q.push({ny,nx});
      dist[idx][ny][nx] = dist[idx][y][x] + 1;
    }
  }
}

int go(int idx, int bit_vector)
{
  if (bit_vector == (1 << (1 + dust_cnt)) - 1) return 0;

  int& ret = dp[idx][bit_vector];
  if (ret != -1) return ret;

  ret = 1e9;

  for (int i = 1; i <= dust_cnt; i++)
  {
    if (bit_vector & (1 << i)) continue;
    int ny = location[i].first;
    int nx = location[i].second;
    if (dist[idx][ny][nx] == -1) continue;
    ret = min(ret, dist[idx][ny][nx] + go(i, bit_vector | (1 << i)));
  }
  return ret;
}

int main()
{
  while(1)
  {
    cin >> w >> h;
    if(w == 0 && h == 0) break;
    dust_cnt = 0;
    memset(dp, -1, sizeof(dp));
    memset(dist, -1, sizeof(dist));

    int sy, sx;
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        cin >> land[i][j];
        if (land[i][j] == '*') {
          location[(dust_cnt++) + 1] = {i, j};
        }
        if (land[i][j] == 'o') {
          location[0] = {i,j};
        }
      }
    }

    for (int i = 0; i <= dust_cnt; i++)
    {
      bfs(i);
    }

    // bit vector = {0, 0, 0, 0, ..., 1}
    // 시작점은 이미 방문했다고 생각하면 된다!
    int ret = go(0, 1);
    if (ret == 1e9) ret = -1;
    cout << ret << endl;
  }
}

 

이 문제는 브루트포스로도 풀 수 있기 때문에 굳이 DP를 사용하지 않아도 되지만, 그래도 외판원 순회 문제를 연습할 수 있는 좋은 문제이다.