(2618) 경찰차

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

단계별로 풀어보기

32단계(동적 계획법과 최단거리 역추적) 5번째

 

 

 

dp[a][b]를 1번 경찰차가 a번 사건 위치에, 2번 경찰차가 b번 사건 위치에 있을 때 남은 사건을 해결하는 거리의 최소라고 하자. (a나 b가 0이면 처음 위치)

이때 다음 i번 사건을 해결할 때 1번 경찰차가 움직이면 dp[i][b]+(a사건 i사건 거리), 2번 경찰차가 움직이면 dp[a][i]+(b사건 i사건 거리)가 된다. 두 사건의 거리는 간단한 공식으로 계산할 수 있고, 두 값 중 더 작은 값을 dp[a][b]에 저장하면 된다.

이를 재귀로 구현하고 dp[0][0]을 구하는 코드를 실행하면 답이 나온다.

역추적은 dp[a][b]를 구하는 과정에서 어떤 경찰차가 움직이는 경우가 더 짧았는지 저장하는 배열을 추가로 만들면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
typedef pair<int,int> p;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, w;
  
  cin >> n >> w;
  
  vector<p> v(w+1);
  vector dp(w+1, vector<int>(w+1, -1));
  vector track(w+1, vector<bool>(w+1));
  
  for(int i=1;i<=w;i++)  cin >> v[i].first >> v[i].second;
  
  auto get_dist= [&](int s, int e, bool isone){
    if(s)  return abs(v[s].first-v[e].first)+abs(v[s].second-v[e].second);
    
    if(isone)  return abs(1-v[e].first)+abs(1-v[e].second);
    else  return abs(n-v[e].first)+abs(n-v[e].second);
  };

  auto func= [&](auto self, int inc, int police1, int police2) -> int {
    if(inc>w)  return 0;
    
    if(dp[police1][police2]!=-1)  return dp[police1][police2];
    
    int val1= self(self, inc+1, inc, police2)+get_dist(police1, inc, true);
    int val2= self(self, inc+1, police1, inc)+get_dist(police2, inc, false);
    
    if(val1<val2){
      track[police1][police2]= true;
      dp[police1][police2]= val1;
    }else{
      track[police1][police2]= false;
      dp[police1][police2]= val2;
    }
    
    return dp[police1][police2];
  };
  
  cout << func(func, 1, 0, 0) << "\n";
  
  for(int i=1,p1=0,p2=0;i<=w;i++){
    if(track[p1][p2]){
      cout << "1\n";
      p1= i;
    }else{
      cout << "2\n";
      p2= i;
    }
  }
  
  return 0;
}

 

 

 

이미 재귀 함수로 dp 계산이 끝났으므로 재귀를 이용해 역추적 할 수도 있다.

함수 track(track, 1, 0, 0)을 호출하면 출동하는 경찰차의 번호가 순서대로 나온다.

  auto track= [&](auto self, int inc, int police1, int police2) -> void {
    if(inc>w)  return;
    
    int cost= func(func, inc+1, inc, police2)+get_dist(police1, inc, true);
    
    if(dp[police1][police2]==cost){
      cout << "1\n";
      self(self, inc+1, inc, police2);
    }else{
      cout << "2\n";
      self(self, inc+1, police1, inc);
    }
    
    return;
  };

 

 

 

아래 코드는 탑다운 방식의 재귀함수 대신 예전 계정에서 바텀업으로 푼 방식이다(약간 수정).

여기서 dp[a][b]는 1번 경찰차가 마지막으로 출동한 사건이 a번, 2번 경찰차가 마지막으로 출동한 사건이 b번일 때 거리의 최소값이다. 대충 어떻게 푸는지 이해는 했는데 아무튼 너무 복잡하다. 그냥 재귀로 푸는 게 나을 것 같다.

#include <iostream>
#include <vector>
using namespace std;
typedef pair<int,int> p;

int main() {
  int n, w;
  
  cin >> n >> w;
  
  vector<p> v(w+1);
  vector dp(w+1, vector<int>(w+1));
  vector from(w+1, vector<p>(w+1));

  for(int i=1;i<=w;i++){
    cin >> v[i].first >> v[i].second;
  }

  dp[1][0]= v[1].first+v[1].second-2;
  dp[0][1]= 2*n-v[1].first-v[1].second;
  for(int i=1;i<w;i++){
    dp[i+1][0]= dp[i][0]+abs(v[i+1].first-v[i].first)+abs(v[i+1].second-v[i].second);
    from[i+1][0]= {i, 0};
    dp[0][i+1]= dp[0][i]+abs(v[i+1].first-v[i].first)+abs(v[i+1].second-v[i].second);
    from[0][i+1]= {0, i};
  }
  
  for(int i=1;i<w;i++){
    dp[i+1][i]= dp[0][i]+v[i+1].first+v[i+1].second-2;
    from[i+1][i]= {0, i};
    dp[i][i+1]= dp[i][0]+2*n-v[i+1].first-v[i+1].second;
    from[i][i+1]= {i, 0};
    for(int j=1;j<i;j++){
      int tmp1= dp[j][i]+abs(v[j].first-v[i+1].first)+abs(v[j].second-v[i+1].second);
      if(dp[i+1][i]>tmp1){
        dp[i+1][i]= tmp1;
        from[i+1][i]= {j, i};
      }
      int tmp2=dp[i][j]+abs(v[j].first-v[i+1].first)+abs(v[j].second-v[i+1].second);
      if(dp[i][i+1]>tmp2){
        dp[i][i+1]= tmp2;
        from[i][i+1]= {i, j};
      }
    }
    for(int j=i+1;j<w;j++){
      dp[j+1][i]= dp[j][i]+abs(v[j+1].first-v[j].first)+abs(v[j+1].second-v[j].second);
      from[j+1][i]= {j, i};
      dp[i][j+1]= dp[i][j]+abs(v[j+1].first-v[j].first)+abs(v[j+1].second-v[j].second);
      from[i][j+1]= {i, j};
    }
  }

  int ans= 20000000;
  p now;
  vector<bool> trace;
  
  for(int i=0;i<w;i++){
    if(ans>dp[i][w]){
      ans= dp[i][w];
      now= {i, w};
    }
    if(ans>dp[w][i]){
      ans= dp[w][i];
      now= {w, i};
    }
  }
  
  cout << ans << "\n";

  while(now.first||now.second){
    p prev= from[now.first][now.second];
    
    trace.push_back(now.first==prev.first);
    
    now= prev;
  }
  
  for(int i=trace.size()-1;i>=0;i--){
    cout << 1+trace[i] << "\n";
  }
  
  return 0;
}