[ICPC] 백준 14961 - Untangling Chain

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

관찰

같은 방향으로 가는 경우가 없다. 무조건 회전한다.

 

어쩌면 이를 이용해서 무언가 할 수 있을지도 않을까?

 

예제 tc 2번을 그려보자.

 

 

이처럼 겹치는 부분이 한 번 발생한다. 이를 해결하려면 어떻게 해야 할까? 가장 명확한 방법은 위에서 2만큼 이동하는 부분을 4로 조정하면 된다.

 

이를 유심히 보자. 밑으로 내려가기 전엔 왼쪽 방향으로 이동을 했었다. 밑으로 내려갈 때 교차가 일어나지 않으려면 왼쪽으로 이동할 때 충분히 이동해야 한다.

 

얼마만큼? 방문했었던 좌표 중에 가장 작은 x 좌표보다 1 이상 더 이동해야 한다.

 

이를 일반화 해보자. 이번에 아래 방향으로 이동을 한 상태라면 다음 이동은 왼쪽 또는 오른쪽으로 할 수밖에 없다. 그러면 우리는 그다음에 왼쪽, 오른쪽으로 이동할 때 교차하지 않도록 거리를 정해야 된다는 소리가 된다.

 

교차하지 않도록 하면 위 예제를 해결할 때와 같이 왼쪽 또는 오른쪽과 교차가 일어나지 않도록 지금까지 방문했던 좌표 중 가장 작은 y 좌표보다 아래로 더 내려가야 한다는 의미가 된다.

 

그러면 위로 갈 때는? 이것도 역시 다음 이동은 왼쪽 또는 오른쪽으로 가야 하므로 가장 큰 y 좌표보다 더 위로 올라가야 한다.

 

나머지 x 방향으로 이동할 때도 똑같다. 여기서는 가장 작은 y와 가장 큰 y 좌표를 신경써주기만 하면 된다.

 

이런 식으로 이동하기만 하면 문제의 제한을 지키면서 교차하지 않는 체인을 만들 수 있게 된다.

구현

위, 오른쪽, 아래쪽, 왼쪽을 각각 0, 1, 2, 3에 대응시키도록 한다. 그러면 입력으로 주어지는 회전 방향 t와 완벽히 대응할 수 있다.

 

나머지 성질을 활용해 -1이 되면 4를 더해 3으로 올리고, 4가 되면 4의 나머지를 취해 0으로 바꾸면 된다. 이렇게 이동 방향을 쉽게 관리할 수 있다.

 

참고로 시작 방향은 오른쪽이므로 1로 초기화 하는 것을 잊지 말자.

 

그러면 각 숫자를 인덱스로 하여금 배열에 대응한다. 그러면 배열에서 해당 인덱스에 해당하는 원소 값은 그 방향으로 갔을 때 최소 혹은 최대 좌표가 된다.

 

현재 시작은 (0, 0)부터 시작한다고 가정하고 현재 위치에서 배열에 대응하는 최대/최소 좌표를 가져와 다음 위치를 구한다. 다음 위치는 그저 1만큼 더하거나 빼면 된다.

 

그러면 현재 좌표와 다음 좌표를 얻으므로 이동거리를 계산할 수 있다. 이동거리를 출력하면 된다.

 

이동 거리 만큼 좌표를 갱신하고 대응하는 배열 원소를 갱신하면서 나아가면 된다. 자세한 구현은 밑을 참조한다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n;
int mx_crd[4];
int dir = 1;
int curx, cury;
 
void solve()
{
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    int len, where;
    cin >> len >> where;
    int mv;
    int nxt;
 
    if (dir == 0)
    {
      nxt = max(mx_crd[dir], cury) + 1;
      mv = nxt - cury;
      cury = nxt;
      mx_crd[dir] = cury;
    }
 
    if (dir == 1)
    {
      nxt = max(mx_crd[dir], curx) + 1;
      mv = nxt - curx;
      curx = nxt;
      mx_crd[dir] = curx;
    }
 
    if (dir == 2)
    {
      nxt = min(cury, mx_crd[dir]) - 1;
      mv = cury - nxt;
      cury = nxt;
      mx_crd[dir] = cury;
    }
 
    if (dir == 3)
    {
      nxt = min(curx, mx_crd[dir]) - 1;
      mv = curx - nxt;
      curx = nxt;
      mx_crd[dir] = curx;
    }
 
    cout << mv << ' ';
    dir += where;
    while (dir < 0) dir += 4;
    dir %= 4;
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록