백준 2873 - 롤러코스터

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

분석

문제를 잘 이해하면 가능한 한 지날 수 있는 모든 칸을 지나야 하는 문제임을 알 수 있다.

 

이 문제의 격자를 체스판으로 생각한다. 시작하는 지점을 흰 칸이라고 가정하자. 그러면 각 이동마다 흰 칸 -> 검은 칸 -> 흰 칸 ->... 이 반복되고 이동을 시작하는 시점에는 지금까지 흰 칸을 지나간 횟수 = 1, 지금까지 검은 칸을 지나간 횟수 = 0 상태가 된다.

 

이를 이해하면 흰 칸을 지나기 위해선 지금까지 흰 칸을 지나간 횟수 = 지금까지 검은 칸을 지나간 횟수를 만족해야 하고 검은 칸을 지나기 위해선 지금까지 흰 칸을 지나간 횟수 + 1 = 검은 칸을 지나간 횟수를 만족해야 함을 알 수 있다.

 

이를 토대로 문제를 해결하기 위해 두 가지 경우를 나눌 수 있다.

행의 갯수가 홀수 또는 열의 개수가 홀수

행의 갯수가개수가 홀수면 시작 지점과 도착 지점의 색이 달라 열 방향, 열의 개수가 홀수면 행 방향으로 지그재그 이동하여 모든 칸을 지나다닐 수 있다.

행의 갯수와 열의 개수가 전부 짝수

이 경우 전체 칸의 갯수는 짝수고 시작 지점의 색과 도착 지점의 색이 같은데 위 분석에 의해 검은 칸 한 칸을 지나지 않아야 도착 지점에 도착할 수 있다.

 

격자를 이동하는 경로를 다시 보면 흰 -> 검 -> 흰 -> 검 -> 흰 순서대로 이동하므로 흰 칸에서 흰 칸에 도착하기 위해서는 검은 칸을 한 칸 덜 지나야 하기 때문이다.

 

이를 통해 한 쪽만 홀수이면 시작 지점과 도착 지점의 색이 달라 몇몇 칸을 덜 지날 필요가 없음을 역시 이해할 수 있다.

 

따라서 우리는 검은 칸에서 최소 숫자를 가진 한 칸을 지나지 않으면 문제를 해결할 수 있다. 먼저 검은 칸 중 최솟값이 있는 격자의 좌표를 기록하도록 한다.

Rook's Tour

사실 진짜 문제는 그 경로를 어떻게 출력하느냐이다. 상하좌우로만 움직일 수 있으므로 룩의 여행으로 볼 수 있는데 행과 열이 모두 짝수임에 착안하여 다음과 같은 전략을 적용할 수 있다.

1. 현재 행과 현재 행의 다음 행에 건너 뛸 칸이 없는 경우

오른쪽 방향으로 쭉 -> 아래로 한 칸 -> 왼쪽으로 쭉 -> 아래로 한 칸...  과 같은 지그재그 이동을 하여 현재 두 행을 바로 지나갈 수 있다. 현재 두 행에 건너뛸 칸이 있을 때까지 지그재그 이동을 실시하면 된다. 이렇게 두 행을 지나 도착한 칸은 흰 칸이다.

 

2. 현재 행 또는 현재 행의 다음 행에 건너 뛸 칸을 마주친 경우

이때는 아래로 한 칸 -> 오른쪽 한 칸 -> 위로 한 칸 -> 오른쪽 한 칸... 지그재그 이동을 한다. 이렇게 두 열을 지나 도착한 칸은 흰 칸이다.

사진은 설명과 반대로 색이 칠해져 있으니 유의

3. 인접한 칸이 건너뛸 칸일 경우

2번 경우의 의해 열을 지나다보면 인접한 검은 칸 중 한 칸이 건너뛸 칸인 경우를 마주친다. 이러면 그저 오른쪽으로 한 칸 움직이면 된다. 그럼 나머지 열들을 2번의 방법과 같은 방법으로 지나갈 수 있게 된다.

4. 2~3번 경우를 모두 지난 경우

그러면 아래쪽으로 한 번 이동한다. 그렇게 되면 왼쪽으로 쭉 -> 아래로 한 칸 -> 오른쪽으로 쭉 -> 아래로 한 칸... 지그재그 이동을 반복하면 도착지에 도착한다.

한쪽이 홀수일 때와 둘 다 짝수일 때 위 전략을 잘 구현하면 정답을 받을 수 있다. 자세한 구현 방법을 모르겠으면 밑의 전체 코드를 참조하도록 한다.

 

전체 코드

#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 pii = pair<int, int>;
using ll = long long;
 
int r, c;
int ar[1000][1000];
int lock_r, lock_c;
string res;
 
void solve()
{
  cin >> r >> c;
 
  if (r & 1)
  {
    bool gor = true;
    for (int i = 0; i < r; i++)
    {
      for (int j = 0; j < c - 1; j++)
      {
        if (gor) res.push_back('R');
        else res.push_back('L');
      }
      if (i != r - 1)
        res.push_back('D');
      gor ^= 1;
    }
    cout << res;
    return;
  }
  else if (c & 1)
  {
    bool god = true;
    for (int i = 0; i < c; i++)
    {
      for (int j = 0; j < r - 1; j++)
      {
        if (god) res.push_back('D');
        else res.push_back('U');
      }
      if (i != c - 1)
        res.push_back('R');
      god ^= 1;
    }
    cout << res;
    return;
  }
 
  int val = 10001;
  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      cin >> ar[i][j];
      if ((i + j) % 2 == 0)
        continue;
      if (val > ar[i][j])
      {
        lock_r = i, lock_c = j;
        val = ar[i][j];
      }
    }
  }
 
  int cur_row = 0, cur_col = 0;
  while (cur_row != lock_r && cur_row + 1 != lock_r)
  {
    for (int i = 0; i < c - 1; i++)
      res.push_back('R');
    res.push_back('D');
    for (int i = 0; i < c - 1; i++)
      res.push_back('L');
    res.push_back('D');
    cur_row += 2;
  }
 
  int mv = 0;
  while (cur_col < c)
  {
    if (cur_col != lock_c)
    {
      if (!mv)
      {
        res.push_back('D');
      }
      else
      {
        res.push_back('U');
      }
      mv ^= 1;
    }
 
    if (cur_col != c - 1)
      res.push_back('R');
    ++cur_col;
  }
  cur_row += 2;
  if (cur_row < r)
    res.push_back('D');
 
  while (cur_row < r)
  {
    for (int i = 0; i < c - 1; i++)
      res.push_back('L');
    res.push_back('D');
    for (int i = 0; i < c - 1; i++)
      res.push_back('R');
    cur_row += 2;
    if (cur_row < r)
      res.push_back('D');
  }
  cout << res;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
 
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록

보너스

앳코더에서는 이와 비슷하게 킹으로 모든 칸을 돌면서 입력으로 제시된 도착 지점에 도착하는 King's tour라는 문제가 있다. 상당히 어려우나 한 번 도전하는 것도 가치 있는 일이 될 것이다.

 

https://atcoder.jp/contests/abc232/tasks/abc232_h

H - King's Tour