BOJ 3043 - 장난감 탱크

BOJ 3043 - 장난감 탱크

우선 $y$ 에 대하여 모두 다르게 만들어둔다.

이후 $x$에 대해 정렬해서 순서에 따라 가야할 위치로 보내주면 된다.

$y$가 정렬된 이후엔 $x$로 이동해도 서로 안 겹치기 때문에 문제가 안되지만, $y$에 대하여 모두 다르게 그리디하게 만들어주는 과정이 까다롭다.

필자같은 경우 $N$이 작음을 이용해서 비효율적으로 한칸한칸 갈 수 있을 때마다 가게 해주었다.

void solve() {  
   int n;  
   cin >> n;  
   vector<pi> a(n);  
   for (auto&[y, x]: a) cin >> y >> x, y--, x--;  
   vector<pair<int, char>> ans;  
   vi idx(n);  
   iota(all(idx), 0);  
   vvi b(n, vi(n, -1));  
   for (int i = 0; i < n; i++) b[a[i].fi][a[i].se] = i;  
  
   sort(all(idx), [&](auto i, auto j) { return a[i].fi < a[j].fi; });  
   vi to_y(n);  
   for (int i = 0; i < n; i++) {  
      to_y[idx[i]] = i;  
   }  
   vi matched(n);  
   int match = 0;  
   while (match != n) {  
      for (int i = 0; i < n; i++) {  
         int I = idx[i];  
         if(matched[I]) continue;  
         if (a[I].fi == to_y[I]) {  
            matched[I] = 1;  
            match++;  
         } else {  
            if (a[I].fi < to_y[I]) {  
               if (b[a[I].fi + 1][a[I].se] == -1) {  
                  b[a[I].fi + 1][a[I].se] = I;  
                  b[a[I].fi][a[I].se] = -1;  
                  a[I].fi++;  
                  ans.pb({I, 'D'});  
               }  
            } else {  
               if (b[a[I].fi - 1][a[I].se] == -1) {  
                  b[a[I].fi - 1][a[I].se] = I;  
                  b[a[I].fi][a[I].se] = -1;  
                  a[I].fi--;  
                  ans.pb({I, 'U'});  
               }  
            }  
         }  
      }  
   }  
  
   vi x_fill(n);  
   idx.clear();  
   for (int i = 0; i < n; i++) {  
      if (!x_fill[a[i].se]) {  
         x_fill[a[i].se] = 1;  
      } else {  
         idx.pb(i);  
      }  
   }  
   vi not_fill;  
   for (int i = 0; i < n; i++) if (!x_fill[i]) not_fill.pb(i);  
   sort(all(idx), [&](int i, int j) { return a[i].se < a[j].se; });  
   for (int i = 0; i < sz(idx); i++) {  
      int I = idx[i];  
      int nxt = not_fill[i];  
      for (int j = a[I].se; j ^ nxt; j < nxt ? j++ : j--) {  
         ans.pb({I, j < nxt ? 'R' : 'L'});  
      }  
   }  
  
   cout << sz(ans) << endl;  
   for (auto[a, b]: ans) cout << a + 1 << ' ' << b << endl;  
}

이 글 에선 좀 더 효율적인 방법을 설명한다.

모든 탱크들을 $y$로 오름차순 정렬해서 자신이 가야할 곳이 더 위인 탱크들은 제일 위부터, 아래로가야하는 탱크들은 제일 아래부터 각각 가야할 위치로 이동시켜주면 교차하는 문제가 발생하지 않게 된다.

void solve() {  
   int n;  
   cin >> n;  
   vector<pi> a(n);  
   for (auto&[y, x]: a) cin >> y >> x, y--, x--;  
   vector<pair<int, char>> ans;  
   vi idx(n);  
   iota(all(idx), 0);  
  
   sort(all(idx), [&](auto i, auto j) { return a[i].fi < a[j].fi; });  
   vi to_y(n);  
   for (int i = 0; i < n; i++) {  
      to_y[idx[i]] = i;  
   }  
  
   vi up, down;  
  
   for (int j = 0; j < n; j++) {  
      if (to_y[idx[j]] > a[idx[j]].fi) down.pb(idx[j]);  
      if (to_y[idx[j]] < a[idx[j]].fi) up.pb(idx[j]);  
   }  
  
   // 위로 가야 하는 탱크들  
   for (int k: up) {  
      while (a[k].fi > to_y[k]) {  
         ans.pb({k, 'U'});  
         a[k].fi--;  
      }  
   }  
   // 아래로 가야 하는 탱크들  
   reverse(all(down));  
   for (int k: down) {  
      while (a[k].fi < to_y[k]) {  
         ans.pb({k, 'D'});  
         a[k].fi++;  
      }  
   }  
  
   vi x_fill(n);  
   idx.clear();  
   for (int i = 0; i < n; i++) {  
      if (!x_fill[a[i].se]) x_fill[a[i].se] = 1;  
      else idx.pb(i);  
   }  
   vi not_fill;  
   for (int i = 0; i < n; i++) if (!x_fill[i]) not_fill.pb(i);  
   sort(all(idx), [&](int i, int j) { return a[i].se < a[j].se; });  
   for (int i = 0; i < sz(idx); i++) {  
      int I = idx[i];  
      int nxt = not_fill[i];  
      for (int j = a[I].se; j ^ nxt; j < nxt ? j++ : j--) {  
         ans.pb({I, j < nxt ? 'R' : 'L'});  
      }  
   }  
  
   cout << sz(ans) << endl;  
   for (auto[a, b]: ans) cout << a + 1 << ' ' << b << endl;  
}