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

문제

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

풀이

너비 우선 탐색

 

간단한 BFS 문제로 기존 문제와 다른 점은 목적지에 도착할 때까지 걸린 count가 필요하다. 

• bool 배열로 해당 칸의 방문 여부를 판별하는 것보다 int 배열로 해당 칸에 도착할 때까지 걸린 count를 기록한다. 
• 방문 여부는 해당 칸의 count가 0인지를 확인하면 된다. 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>

using namespace std;

int T;
int I;
// visited 배열이 아닌 int로 count와 방문 여부를 동시 관리
int moveCount[300][300];

int moveX[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int moveY[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> T;

	memset(moveCount, 0, sizeof(moveCount));

	while (T--)
	{
		int startX, startY, destX, destY;
		queue<pair<int, int>> q;

		cin >> I;
		cin >> startX >> startY >> destX >> destY;

		q.push(make_pair(startX, startY));

		while (false == q.empty())
		{
			int currentX = q.front().first;
			int currentY = q.front().second;
			q.pop();

			if (destX == currentX && destY == currentY)
			{
				cout << moveCount[currentX][currentY] << '\n';
				break;
			}

			for (int i = 0; i < 8; ++i)
			{
				int nextX = currentX + moveX[i];
				int nextY = currentY + moveY[i];

				// moveCount가 0이 아닌 경우는 이미 방문한 칸이므로 continue 처리
				if (nextX < 0 || nextX >= I || nextY < 0 || nextY >= I || 0 != moveCount[nextX][nextY])
				{
					continue;
				}

				q.push(make_pair(nextX, nextY));
				moveCount[nextX][nextY] = moveCount[currentX][currentY] + 1;
			}
		}

		memset(moveCount, 0, sizeof(moveCount));
	}

	return 0;
}