BaekJoon 7562 나이트의 이동

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

소스결과 1988KB 48ms

출처 Backjoon, TUD(Tu-Darmstadt) Programming Contest Contest 2001 3번

언어 C++17

 

설명

기본 BFS가 4방향인 점과는 다르게 8방향이고 인접한 칸으로 이동하는 것이 아닌 몇칸 떨어져 있는 위치로 이동하는 것이 특징

이전 BFS문제와 똑같이 구현하고 방향성을 8개로 늘리고 값만 조금 수정하는 것과는 크게 차이가 없는 문제

 

4방향 BFS를 if - else 문을 통해 구현 했다면 코드가 조금 길어지겠지만, 위치를 기억하는 배열이 있다면 그부분만 수정하면 된다.

한변의 최대 길이를 100으로 착각하지만 않았으면 한번에 맞췄을텐데 아쉽다.

 

알고리즘

1. 테스트 케이스를 입력 받는다.

2. 한변의 길이, 시작지점, 목표 지점을 받은 후 해당 케이스에 대해서 BFS를 진행

3. 결과를 출력

4. 테스트 케이스 만큼 반복한다.

 

소스코드

#include <iostream>
#include <queue>

using namespace std;

const short posX[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
const short posY[8] = { -2, -1, 1 ,2 , 2, 1, -1, -2 };

struct Point {
	short x;
	short y;

	Point() {}
	Point(short x, short y) : x(x), y(y) {}
};

int solution(int n, Point start, Point des)
{
	bool check[301][301];
	queue<Point> currentQ;
	queue<Point> nextQ;
	int result = 0;
	bool isFind = false;

	for (int i = 0; i < n; i++)
		fill_n(check[i], n, false);

	currentQ.push(start);

	while (!isFind)
	{
		while (!currentQ.empty())
		{
			Point cur = currentQ.front();
			currentQ.pop();

			if (cur.x == des.x && cur.y == des.y)
			{
				isFind = true;
				break;
			}

			if (check[cur.x][cur.y])
				continue;

			check[cur.x][cur.y] = true;

			for (int i = 0; i < 8; i++)
			{
				int nextX = cur.x + posX[i];
				int nextY = cur.y + posY[i];

				if (0 <= nextX && nextX < n && 0 <= nextY && nextY < n && !check[nextX][nextY])
					nextQ.push(Point(nextX, nextY));
			}
		}

		if (isFind)
			break;

		while (!nextQ.empty())
		{
			currentQ.push(nextQ.front());
			nextQ.pop();
		}
		result++;
	}

	return result;
}

int main()
{
	int tcc;

	cin >> tcc;

	for (int i = 0; i < tcc; i++)
	{
		int l;
		short x1, y1, x2, y2;

		cin >> l >> x1 >> y1 >> x2 >> y2;

		int res = solution(l, Point(x1, y1), Point(x2, y2));
		cout << res << endl;
	}

	return 0;
}