백준 16959번 체스판 여행 1 문제 해설


문제 링크

solved.ac 기준 골드 1 난이도의 문제입니다. BFS 개념과 구현 능력을 평가하기에 좋은 문제였습니다.

일반적인 BFS, 구현 문제와 달리 체스판 과 체스말 이라는 특정한 조건에서 최소 이동 경로를 구할수 있는지 에 관한 문제입니다.


문제


크기가 N×N인 체스판이 있고, 체스판의 각 칸에는 1부터 N2까지의 정수가 한 번씩 적혀있다. 
지학이는 이 체스판을 이용해서 재미있는 게임을 해보려고 한다.

지학이가 가지고 있는 말은 나이트, 비숍, 룩이다. 가장 먼저 1이 적혀있는 칸에 말 하나를 놓는다. 
그 다음, 1, 2, ..., N2 순서로 이동시키려고 한다.

먼저, 1에 나이트, 비숍, 룩 중 하나를 놓는다. 그 다음, 말을 이동시켜서 2가 적힌 칸으로 이동시킨다. 
1에서 2로 이동시킬 때, 다른 수가 적힌 칸을 방문할 수도 있다. 그 다음에는 3이 적힌 칸으로 이동시키고,
 ..., N2이 적힌 칸으로 이동시킨다. 같은 칸을 여러 번 방문하는 것도 가능하다.

지학이가 1초 동안 할 수 있는 행동은 체스판 위에 놓인 말을 이동시키거나, 다른 말로 바꾸는 것이다.

1에서 출발해서, 2, 3, ..., N2-1을 방문하고, N2까지 도착하는데 걸리는 시간의 최솟값을 구해보자.

입력

첫째 줄에 체스판의 크기 N(3 ≤ N ≤ 10)이 주어진다.
둘째 줄부터 N개의 줄에 체스판에 적힌 수가 주어진다.

출력

첫째 줄에 문제에 주어진 대로 방문하는데 필요한 시간의 최솟값을 출력한다. 

예제입력

5
21 14 2 3 12
19 8 16 18 7
9 17 10 15 4
24 5 1 23 11
25 13 22 6 20

예제출력

38


문제 풀이


이 문제에서 어려웠던 점은, 일반적으로 BFS 문제 에서는 이동 경로가 한 번에 상, 하, 좌, 우 1칸 으로 한정되어 있는 것 에 반해 체스판 과 체스말 이라는 특수한 조건 존재한다는 점 이였습니다.

문제를 해결하기에 앞서 우선 체스판 에서 체스말 (룩, 비숍, 나이트) 들이 어떤 규칙을 따라서 이동할 수 있는지 부터 그림으로 살펴보겠습니다.


그림1 체스말이 각각 룩, 비숍, 나이트 일 때에 체스의 규칙에 따라서 한번에 이동할 수 있는 경우를 나타내 보았습니다.


이제 체스말 들이 각각 어떻게 움직이는지 알았으니, 현재 상태에서 어떤 행동들을 취할 수 있는지 알아보겠습니다. 문제의 조건에서 지학이가 1초 동안 할 수 있는 행동은 체스판 위에 놓인 말을 이동시키거나, 다른 말로 바꾸는 것이다. 라고 명시되어 있네요!

현재 상태에서 할 수 있는 행동은 체스말을 다른 말로 바꾸거나, 규칙에 따라서 이동시키거나 2가지 밖에 존재하지 않습니다. 그림으로 살펴보면 다음과 같습니다.


그림2 현재 상태에서 할 수 있는 행동은 2가지 밖에 존재하지 않습니다.


그렇다면, 현재 할 수 있는 행동인 말을 바꾸거나, 말을 이동시키 거나 를 계속 실행 해 가며 처음 칸 에서 최종 목적지 칸 까지 도달할 때 까지 반복하면 이 문제를 해결할 수 있을것 같네요.

이런식으로 실행한다면, 제한시간 안에 문제를 해결할 수 있을까요? 과연 얼마나 오랬동안 말을 바꾸고 이동시켜야 최종 목적지에 도달할 수 있을까요?


그림3 체스말 중 나이트를 이동할 때 의 예시를 들어보겠습니다.

체스판의 크기가 가로, 세로 최대 10 칸 으로 문제에서 주어져 있으므로, 현재 숫자가 1 이고 다음 숫자인 2 를 찾아서 나이트가 이동 할 때 체스판의 전체 넓이인 100칸을 모두 밟아 본다면 무조건 다음 숫자를 찾을 수 있음을 보장할 수 있습니다.

체스판 안 어딘가에 다음 숫자가 있으니, 체스판 전체인 100칸을 모두 밟아보면 다음 숫자를 무조건 찾을수 있죠!

체스말의 종류가 3가지 이므로 현재 숫자에서 다음 숫자까지 밟아야 하는 칸은 각각 최대 100칸 씩 3 x 100 = 300칸 이며 체스판의 최대 크기가 100 이므로 최종 숫자의 최대값도 100 이므로 300칸 x 100 = 30000 번 만 체스말을 이동 시켜 보면 1 부터 100 까지의 이동경로를 무조건 찾을 수 있습니다.

하지만, 이때 현재 상태에서 다음 숫자를 찾아가는 과정에서 지나온 칸은 다시 가지 않는다는 조건이 꼭 필요합니다.

이 조건이 없다면 룩이 한칸씩 좌우로 계속 움직일 수 있으므로, 당연히 시간 초과가 발생할 것 입니다.


그림4 현재 상태에서 다음 숫자를 향해 이동할 때 지나온 칸 을 다시 밟지 않으려면, Visited 배열을 만들어 지나온 칸 들을 표시하면 됩니다.

이때 현재 상태를 표현하기 위해선 체스말의 X좌표, Y좌표, 다음 숫자, 체스말 종류 정보가 필요합니다.

X좌표와 Y좌표는 당연히 필요하며 체스말 종류는 룩, 비숍, 나이트 의 이동 경로를 따로 세기 위함 입니다.

다음숫자가 필요한 이유는, 1 에서 2 로 이동할 때 체스말이 밟았던 이동 경로를 2 에서 3 으로 이동할 때 다시 갈 수 있도록 문제에 조건에서 주어졌기 때문입니다. 방문한 칸은 다시 방문할 수 있죠.

따라서 1 에서 2 로 이동할때 만 밟았던 칸, 2 에서 3 으로 이동할때 만 밟았던 칸 을 따로 따로 표시하기 위해 다음 숫자가 필요한 것 입니다.


여기까지 문제의 해결 방법을 모두 생각해 보았습니다.

체스말의 이동 경로를 알아본 후 현재 상태에서 할 수 있는 행동을 알아봤으며 이때 Visited 배열로 지나온 칸을 표시하여 제한 시간 안에 문제를 해결할 수있는 방법을 찾을 수 있었네요.

여기까지의 아이디어를 그대로 코드로 구현해보겠습니다!


소스코드


#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>

using namespace std;

const int knight_dX[8] = { -2, -2, 2, 2, -1, -1, 1, 1 };
const int knight_dY[8] = { -1, 1, -1, 1, -2, 2, -2, 2 };

const int bishop_dX[4] = { -1, -1, 1, 1 };
const int bishop_dY[4] = { -1, 1, -1, 1 };

const int rook_dX[4] = { -1, 0, 1, 0 };
const int rook_dY[4] = { 0, -1, 0, 1 };

int row, col;

int map[11][11];
bool visited[11][11][111][4];

int locationX[111];
int locationY[111];

const int ROOK = 0;
const int BISHOP = 1;
const int KNIGHT = 2;

const int MAXLIFE = 3;

class chessPiece
{
public:
	int x, y, count, next, pieceType;

	chessPiece(int x, int y, int count, int next, int pieceType)
		:x(x), y(y), count(count), next(next), pieceType(pieceType) {};
};

int min = 987654321;

void bfs(int startX, int startY)
{
	queue<chessPiece> q;

	q.push(chessPiece(startX, startY, 0, 2, ROOK));
	q.push(chessPiece(startX, startY, 0, 2, BISHOP));
	q.push(chessPiece(startX, startY, 0, 2, KNIGHT));

	visited[startX][startY][2][ROOK] = true;
	visited[startX][startY][2][BISHOP] = true;
	visited[startX][startY][2][KNIGHT] = true;

	while (q.empty() == false)
	{
		chessPiece curPiece = q.front();

		int curX = curPiece.x;
		int curY = curPiece.y;
		int count = curPiece.count;
		int next = curPiece.next;
		int pieceType = curPiece.pieceType;

		int nextX = locationX[next];
		int nextY = locationY[next];

		q.pop();

		// 마지막 숫자에 도달한 경우
		if (next == row * col + 1)
		{
			if (::min > count)
				::min = count;

			return;
		}

		// 말을 바꿈
		for (int i = 0; i < 3; i++)
		{
			if (i == pieceType)
				continue;

			if (visited[curX][curY][next][i])
				continue;

			visited[curX][curY][next][i] = true;
			q.push(chessPiece(curX, curY, count + 1, next, i));
		}

		// 현재 말이 룩 일때
		if (pieceType == ROOK)
		{
			for (int i = 0; i < 4; i++)
			{
				for (int offset = 1; ; offset++)
				{
					int nX = curX + rook_dX[i] * offset;
					int nY = curY + rook_dY[i] * offset;

					if (nX < 0 || nX >= row || nY < 0 || nY >= col)
						break;

					if (visited[nX][nY][next][ROOK])
						continue;

					visited[nX][nY][next][ROOK] = true;

					if (nX == nextX && nY == nextY)
					{
						q.push(chessPiece(nX, nY, count + 1, next + 1, ROOK));
					}
					else
						q.push(chessPiece(nX, nY, count + 1, next, ROOK));
				}
			}
		}
		// 현재 말이 비숍 일때
		else if (pieceType == BISHOP)
		{
			for (int i = 0; i < 4; i++)
			{
				for (int offset = 1; ; offset++)
				{
					int nX = curX + bishop_dX[i] * offset;
					int nY = curY + bishop_dY[i] * offset;

					if (nX < 0 || nX >= row || nY < 0 || nY >= col)
						break;

					if (visited[nX][nY][next][BISHOP])
						continue;

					visited[nX][nY][next][BISHOP] = true;

					if (nX == nextX && nY == nextY)
					{
						q.push(chessPiece(nX, nY, count + 1, next + 1, BISHOP));
					}
					else
						q.push(chessPiece(nX, nY, count + 1, next, BISHOP));
				}
			}
		}
		// 현재 말이 비숍 일때
		else if (pieceType == KNIGHT)
		{
			for (int i = 0; i < 8; i++)
			{
				int nX = curX + knight_dX[i];
				int nY = curY + knight_dY[i];

				if (nX < 0 || nX >= row || nY < 0 || nY >= col)
					continue;

				if (visited[nX][nY][next][KNIGHT])
					continue;

				visited[nX][nY][next][KNIGHT] = true;

				if (nX == nextX && nY == nextY)
				{
					q.push(chessPiece(nX, nY, count + 1, next + 1, KNIGHT));
				}
				else
					q.push(chessPiece(nX, nY, count + 1, next, KNIGHT));
			}
		}


	}
}

void solve()
{
	int startX = -1, startY = -1;

	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
			if (map[i][j] == 1)
			{
				startX = i, startY = j;
				break;
			}

	bfs(startX, startY);

	cout << ::min << endl;
}

int main()
{
	memset(visited, false, sizeof(visited));

	cin >> row;	col = row;

	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
		{
			cin >> map[i][j];

			locationX[map[i][j]] = i;
			locationY[map[i][j]] = j;
		}

	solve();

	return 0;
}

문제의 접근방식과 아이디어를 그대로 소스코드로 구현하였습니다.

채점결과


주의할 점


소스코드 에서 룩, 비숍의 이동경로를 이동 방향에 따라 한칸 한칸 모두 넣어주었습니다.

처음에는 이렇게 구현하지 않고 룩을 목적지까지 한번에 이동시키도록 구현하였는데, 예외케이스가 있었습니다.

비숍 -> 이동 -> 룩으로 변경 -> 이동 처럼 이동 중간에 다른 말로 변경하는 경우가 존재하므로, 룩을 목적지 까지 쭉 한번에 이동시키면 안되고, 이동하는 경로 한 칸 한 칸을 모두 큐에 넣어주어야 예외케이스 없이 정상적으로 작동하게 됩니다.

비숍도 마찬가지 입니다.


더 빠른 실행 속도를 원하신다면..


BFS를 기반으로 구현하였으므로, 최종 목적지에 도착하면 그 때의 거리가 최소 이동 거리 임은 보장됩니다.

이때 어떻게 더 최적화 할 수 있을까요?

힌트는, 각 체스말의 다음 숫자로 갈 때의 최대 이동 수는 3 이다 를 활용하는 것 입니다.

왜 3일까요? 그 답은, 현재 말이 어떤 말 이던 룩으로 바꾸고 (+1 회) 가로로 쭉 이동하고 (+1 회) 세로로 쭉 이동하면 (+1 회) 현재의 숫자와 목적지 숫자의 배치가 어떻던 상관없이 무조건 적으로 3회 안에 다음 숫자로 이동할 수 있기 때문이죠!

따라서, 3회를 초과하여 이동하는 경우는 룩으로 바꾸고 3회안에 이동하는 더 짧은 경로가 무조건 적으로 존재하므로, 더 이상 이동시키지 않아도 최단거리가 아님을 알 수 있습니다.

이러한 방식으로 가지치기를 하여 탐색 시간을 줄일 수 있습니다.

하지만, 문제에서 체스판의 최대 크기가 10 x 10 이므로 가지치기를 하지 않아도 제한시간 안에 충분히 통과할 수 있었습니다.


문제풀이 후기


이 문제는 체스판, 체스말 이라는 특수한 조건에서 BFS를 구현하는 문제였습니다.

전형적인 BFS 문제는 아니였지만, BFS 의 개념을 잘 알고계신 분 이라면 해결할 수 있을 것 이라고 생각합니다.

최적화 방법도 제가 생각한 방법 말고도 다른 방법이 많이 존재할 것 같습니다!

더 빠른 해결 방법을 찾는다면 하단의 메일로 연락주시면 아이디어를 추가해 놓겠습니다!

감사합니다.