[백준 7562] 나이트의 이동 (C++)

문제

---

 

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

 

입력

---

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

 

출력

---

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

문제 풀이

---

bfs 기본 문제.

너비 우선 탐색을 통해 몇 번만에 이동할 수 있는지 구한다. bfs는 큐를 이용하여 구현할 수 있는데, x좌표, y좌표, 현재 몇 번 이동했는지를 나타내는 구조체를 만들어 해당 타입으로 큐를 생성한다. 또한 무한히 같은 칸들을 탐색하지 않도록 이미 방문했는지를 체크하는 2차원 배열 isVisited을 만든다.

나이트의 출발점 위치와 0번 이동했음을 나타내는 구조체를 큐에 넣고 탐색한다. 현재 큐의 맨 앞에 위치한 구조체로부터 위치를 받아와 나이트가 이동할 수 있는 8칸을 체스판 범위를 넘어가는지와 이미 방문한 칸인지를 체크한다. 범위를 넘어가지 않고 이미 방문하지 않은 칸이라면 해당 칸을 큐에 넣고 해당 칸에 해당하는 isVisited칸을 true로 바꾸어 방문했음을 알린다.

이동할 수 있는 8칸을 모두 탐색하면 현재 칸으로부터 탐색할 수 있는 모든 칸을 탐색했으므로 큐에서 빼내준다.

현재 칸이 나이트가 이동하려고 하는 칸이라면 몇 번만에 이동했는지를 출력한다.

 

여러개의 테스트 케이스가 있으므로 bfs 탐색 전 큐를 모두 비우고, isVisited 배열을 보드 칸* 보드 칸만큼 false로 초기화해준다.

 

#include <iostream>
#include <queue>
using namespace std;
int board[301][301];
bool isVisited[301][301];
int boardSize;
int dx[] = { -2, -2, -1, -1, 1, 1, 2, 2 };
int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
int knightX, knightY;
int endX, endY;

struct info
{
	int x;
	int y;
	int count;
	info(int a, int b, int c)
	{
		x = a;
		y = b;
		count = c;
	}
};
queue<info> bfsQueue;

void bfs()
{
	bfsQueue.push(info(knightX, knightY, 0));
	isVisited[knightX][knightY] = true;
	while (!bfsQueue.empty())
	{
		info currentFront = bfsQueue.front();
		if (currentFront.x == endX && currentFront.y == endY)
		{
			cout << currentFront.count << "\n";
		}
		for (int i = 0; i < 8; i++)
		{
			int nextX = currentFront.x + dx[i];
			int nextY = currentFront.y + dy[i];
			if (nextX >= 0 && nextX < boardSize && nextY >= 0 && nextY < boardSize && isVisited[nextX][nextY] == false)
			{
				isVisited[nextX][nextY] = true;
				bfsQueue.push(info(nextX, nextY, currentFront.count + 1));
			}
		}
		bfsQueue.pop();
	}
}

void reset()
{
	while (!bfsQueue.empty())
	{
		bfsQueue.pop();
	}
	for (int i = 0; i< boardSize; i++)
	{
		for (int j = 0; j < boardSize; j++)
		{
			isVisited[i][j] = false;
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int T;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		reset();
		cin >> boardSize;
		cin >> knightX >> knightY;
		cin >> endX >> endY;
		bfs();
	}

	return 0;
}