BOJ 28285 - 육각형 순회

BOJ 28285 - 육각형 순회

$(1,1)$ 에서 시작하는 싸이클을 항상 그릴 수 있다. 레벨이 같은 쪽으로 순회하다가 갈 곳이 없으면 한 단계 낮추고를 반복하여 $(n, n)$ 까지 쭉 간다음에 거기서는 $(1,1)$ 까지 $n-1$ 개의 왼쪽 위로 가주면 된다.

이러한 싸이클을 항상 찾을 수 있으므로 초기 위치에서 시작하게 만드려면 원래 정답에서 초기 위치가 시작하는 부분으로 rotate 시켜주면 된다.

이런 벌집모양 문제를 풀 때 모든 벌집마다 level을 미리 기록해두는 방법을 사용하는데, 이 방법은 좀 느린것같다.

게다가 이 문제는 $dy,dx$ 를 이용해 풀기에는 $dx$가 $y$에 따라 계속 달라져서 왜 안되지하고 한참 헤맸다.

string dir = "QEDCZA";  
int dy[] = {-1, -1, 0, 1, 1, 0};  
int dx_up[] = {-1, 0, 1, 1, 0, -1};  
int dx_mid[] = {-1, 0, 1, 0, -1, -1};  
int dx_down[] = {0, 1, 1, 0, -1, -1};  
  
int n, lv[2222][2222], vis[2222][2222];  
int rc(int y) {  
   return 2 * n - 1 - abs(y - n);  
}  
int in(int y, int x) {  
   return y >= 1 && y <= 2 * n - 1 && x >= 1 && x <= rc(y);  
}  
void solve() {  
   cin >> n;  
  
   auto get_dx = [&](int y) {  
      if (y == n) return dx_mid;  
      if (y < n) return dx_up;  
      return dx_down;  
   };  
  
   lv[n][n] = 1;  
   queue<pi> q;  
   q.push({n, n});  
   while (sz(q)) {  
      auto [y, x] = q.front();  
      q.pop();  
      for (int d = 0; d < 6; d++) {  
         int ny = y + dy[d], nx = x + get_dx(y)[d];  
         if (in(ny, nx) && lv[ny][nx] == 0) {  
            lv[ny][nx] = lv[y][x] + 1;  
            q.push({ny, nx});  
         }  
      }  
   }  
   int sy, sx;  
   cin >> sy >> sx;  
   string ans;  
   int y = 1, x = 1;  
   vis[1][1] = 1;  
  
   do {  
      for (int diff: {0, -1}) {  
         for (int d = 0; d < 6; d++) {  
            int ny = y + dy[d], nx = x + get_dx(y)[d];  
  
            if (in(ny, nx) && lv[ny][nx] == lv[y][x] + diff && !vis[ny][nx]) {  
  
               if (ny == nx) {  
                  if (ny < n) continue;  
               }  
  
               y = ny, x = nx;  
               vis[y][x] = 1;  
               ans += dir[d];  
               goto out;  
            }  
         }  
      }  
      out:;  
   } while (y != n || x != n);  
   while (y != 1) {  
      ans += 'Q';  
      y--;  
      x--;  
      vis[y][x] = 1;  
   }  
   int offset = -1;  
   y = 1, x = 1;  
   for (int i = 0;; i++) {  
      if (y == sy && x == sx) {  
         offset = i;  
         break;  
      }  
      int d = dir.find(ans[i]);  
      int ny = y + dy[d];  
      int nx = x + get_dx(y)[d];  
      y = ny;  
      x = nx;  
   }  
   rotate(ans.begin(), ans.begin() + offset, ans.end());  
  
   cout << ans;  
}