체스판 여행 1

Problem link: https://www.acmicpc.net/problem/16959

처음에 DP + Floyd로 해결할 수 있을 것이라고 착각했다가 꽤 오랜 시간을 허비했다.

문제를 잘못 이해했을 뿐 나름 나쁘지 않은 접근이었기 때문에, 제대로 된 풀이를 기술한 뒤에 DP + Floyd 풀이와, 왜 안되는지를 적어보고자 한다.

제대로 된 풀이를 기술하면, 레이저 통신 문제에서와 유사하게 BFS를 잘 응용해주면 풀 수 있는 문제이다.

단, 이때 방문했던 정점을 다시 방문할 수 있으므로 visit 배열을 단순하게 visit[row][col]로 표현하지 않고, visit[row][col][밟고자 하는 수][체스말의 종류]와 같이 표현해주었다.

각 위치에서 말을 바꾸지 않고 이동하는 경우들을 모두 push해주고, 또 말을 바꾸는 경우들을 모두 push해준다.

이렇게 하면 큐는 앞에 위치할 수록 시간이 덜 걸리는 경우임이 보장되기 때문에, 큐에서 가장 먼저 목적지에 도착하는 경우가 곧 최소시간이 된다.

한편, DP + Floyd는 아래의 아이디어를 활용했었는데, 결과적으로는 문제 해석을 잘못한 경우로 이 풀이가 틀린 이유는 마지막에 기술한다.

---

DP + Floyd를 아용하여 풀었다.

문제의 조건에 의해 항상 n번 -> n+1번 순서로 방문을 진행해야하며 중간에 방문하게 되는 칸들은 의미가 없다.

이는 n번 -> n+1번을 방문할 때 굳이 최단 시간이 아닌 방법을 사용하지 않을 필요가 없을 의미한다.

따라서, n번 -> n+1번 방문 시에는 각 말로 최단 시간이 걸리는 방법을 이용해서 이동하는 것으로 생각하자.

이 때, 각 말에 따라서 n번 -> n+1번 지점 방문에 소요되는 최소 시간을 구해 놓기 위하여 Floyd-Warshall을 활용한다.

편의상 후술에서는 Floyd-Warshall을 통해 구한 최단 거리가 아래와 같이 정의된다고 하자.

• DIST[i][j][k]: i번 지점에서 j번 지점까지 k말(0:=knight, 1:=bishop, 2:=rook)로 이동할 때 최단 소요 시간

본격적으로 이를 사용한 DP 풀이를 만들어 보도록 하자.

CACHE는 아래와 같이 정의한다.

• CACHE[i][k]: i번 째 지점에 k말로(0:=knight, 1:=bishop, 2:=rook) 도착할 때 최소의 소요시간

그럼 점화식은 아래와 같이 도출할 수 있다.

편의상 k == 1인 경우에 대해서만 기술한다.

• CACHE[i][1] = min(CACHE[i-1][0] + 1, CACHE[i-1][1], CACHE[i-1][2] + 1) + DIST[i-1][i][1]

식을 한 항씩 살펴보면 별게 없는데, 각각

• knight로 i-1번 지점까지 오다가 bishop으로 바꿔서 오는 경우
• bishop으로 i-1번 지점까지 오다가 bishop으로 오는 경우(말을 바꾸지 않음)
• rook으로 i-1번 지점까지 오다가 bishop으로 오는 경우

이 풀이가 틀린 이유는 문제에 있는 " 1에서 2로 이동시킬 때, 다른 수가 적힌 칸을 방문할 수도 있다." 표현 때문이다.

위의 풀이를 보면 1 -> 2 -> 3의 이동에서 비숍의 1회 1->3 이동으로 달성가능한 경우를 1->2, 2->3과 같이 2회 이동으로 처리하고 있는 것을 알 수 있다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

const int kMaxN = 10;
const int kKnight = 0;
const int kBishop = 1;
const int kRook = 2;
const int kNumOfPieceKinds = 3;

struct Piece
{
  int row;
  int col;
  int kind;
  int target;
  int elapsed;

  Piece(const int row, const int col, const int kind, const int target, const int elapsed)
    : row(row), col(col), kind(kind), target(target), elapsed(elapsed)
  {
  }
};

int N;
int BOARD[kMaxN][kMaxN];
map<int, pair<int, int> > POS;

int Bfs(void)
{
  bool visit[kMaxN][kMaxN][kMaxN * kMaxN + 1][kNumOfPieceKinds] = {
    false,
  };
  queue<Piece> q;

  visit[POS[1].first][POS[1].second][1][kKnight] = true;
  visit[POS[1].first][POS[1].second][1][kBishop] = true;
  visit[POS[1].first][POS[1].second][1][kRook] = true;

  q.emplace(POS[1].first, POS[1].second, kBishop, 2, 0);
  q.emplace(POS[1].first, POS[1].second, kRook, 2, 0);
  q.emplace(POS[1].first, POS[1].second, kKnight, 2, 0);

  int ans = -1;

  while (!q.empty())
  {
    Piece current = q.front();
    q.pop();

    if (current.target == N * N && BOARD[current.row][current.col] == N * N)
    {
      ans = current.elapsed;
      break;
    }

    int ntarget = current.target;
    if (BOARD[current.row][current.col] == current.target)
    {
      ntarget = ntarget + 1;
    }

    if (current.kind == kKnight)
    {
      const int dr[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
      const int dc[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

      for (int dir = 0; dir < 8; ++dir)
      {
        int nrow = current.row + dr[dir];
        int ncol = current.col + dc[dir];
        if (0 <= nrow && nrow < N && 0 <= ncol && ncol < N)
        {
          if (!visit[nrow][ncol][ntarget][kKnight])
          {
            visit[nrow][ncol][ntarget][kKnight] = true;
            q.emplace(nrow, ncol, kKnight, ntarget, current.elapsed + 1);
          }
        }
      }

      if (!visit[current.row][current.col][ntarget][kBishop])
      {
        visit[current.row][current.col][ntarget][kBishop] = true;
        q.emplace(current.row, current.col, kBishop, ntarget, current.elapsed + 1);
      }

      if (!visit[current.row][current.col][ntarget][kRook])
      {
        visit[current.row][current.col][ntarget][kRook] = true;
        q.emplace(current.row, current.col, kRook, ntarget, current.elapsed + 1);
      }
    }
    else if (current.kind == kBishop)
    {
      const int dr[4] = { -1, 1, 1, -1 };
      const int dc[4] = { 1, 1, -1, -1 };

      for (int dir = 0; dir < 4; ++dir)
      {
        int nrow = current.row;
        int ncol = current.col;
        while (true)
        {
          nrow += dr[dir];
          ncol += dc[dir];
          if (0 <= nrow && nrow < N && 0 <= ncol && ncol < N)
          {
            if (!visit[nrow][ncol][ntarget][kBishop])
            {
              visit[nrow][ncol][ntarget][kBishop] = true;
              q.emplace(nrow, ncol, kBishop, ntarget, current.elapsed + 1);
            }
          }
          else
          {
            break;
          }
        }
      }

      if (!visit[current.row][current.col][ntarget][kKnight])
      {
        visit[current.row][current.col][ntarget][kKnight] = true;
        q.emplace(current.row, current.col, kKnight, ntarget, current.elapsed + 1);
      }

      if (!visit[current.row][current.col][ntarget][kRook])
      {
        visit[current.row][current.col][ntarget][kRook] = true;
        q.emplace(current.row, current.col, kRook, ntarget, current.elapsed + 1);
      }
    }
    else if (current.kind == kRook)
    {
      const int dr[4] = { -1, 0, 1, 0 };
      const int dc[4] = { 0, 1, 0, -1 };

      for (int dir = 0; dir < 4; ++dir)
      {
        int nrow = current.row;
        int ncol = current.col;
        while (true)
        {
          nrow += dr[dir];
          ncol += dc[dir];
          if (0 <= nrow && nrow < N && 0 <= ncol && ncol < N)
          {
            if (!visit[nrow][ncol][ntarget][kRook])
            {
              visit[nrow][ncol][ntarget][kRook] = true;
              q.emplace(nrow, ncol, kRook, ntarget, current.elapsed + 1);
            }
          }
          else
          {
            break;
          }
        }
      }

      if (!visit[current.row][current.col][ntarget][kKnight])
      {
        visit[current.row][current.col][ntarget][kKnight] = true;
        q.emplace(current.row, current.col, kKnight, ntarget, current.elapsed + 1);
      }

      if (!visit[current.row][current.col][ntarget][kBishop])
      {
        visit[current.row][current.col][ntarget][kBishop] = true;
        q.emplace(current.row, current.col, kBishop, ntarget, current.elapsed + 1);
      }
    }
  }

  return ans;
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  cin >> N;
  for (int i = 0; i < N * N; ++i)
  {
    cin >> BOARD[i / N][i % N];
    POS[BOARD[i / N][i % N]] = pair<int, int>(i / N, i % N);
  }

  // Solve
  cout << Bfs() << '\n';

  return 0;
}