백준 7562번 - 나이트의 이동

7562번: 나이트의 이동 (acmicpc.net)

7562번: 나이트의 이동

체스판에서 나이트가 갈 수 있는 위치는 8곳이다.

첫 줄에 테스트 케이스의 수가 주어지고 , 테스트 케이스마다 나이트의 현재위치에서 이동 할 칸까지 최소 몇번만에 갈수있는지를 출력하면 된다.

#include<iostream>
#include<queue>
#include<utility>
using namespace std;

//거리를 담을 배열
int dist[300][300];

//상하 좌우 탐색을 도와주는 배열
int dx[8] = { -2,-2,2,2,-1,1,-1,1 };
int dy[8] = { -1,1,-1,1,-2,-2,2,2 };

int testcase;
int n;
int x, y;

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

	cin >> testcase;

	while (testcase--)
	{

		queue<pair<int, int>> Q;

		cin >> n;
		
        //dist배열 초기화
		for (int i = 0; i < n; i++) 
			fill(dist[i], dist[i] + n, 0);
		
        //나이트 좌표
		cin >> x >> y;

		dist[x][y] = 1;
		Q.push({ x, y });
		
        //이동할 좌표
		cin >> x >> y;

		while (!Q.empty())
		{
			auto cur = Q.front(); Q.pop();
			for (int i = 0; i < 8; i++)
			{
				int dirX = cur.first + dx[i];
				int dirY = cur.second + dy[i];
				
                //배열의 인덱스를 벗어나면 컨티뉴
				if (dirX < 0 || dirY < 0 || dirX >= n || dirY >= n) continue;
				// 이미 탐색해서 값을 넣은 곳이면 컨티뉴
				if (dist[dirX][dirY] > 0) continue;
				
                //현재 위치+1을 넣어줌
				dist[dirX][dirY] = dist[cur.first][cur.second] + 1;
				Q.push({ dirX ,dirY });
			}
		}
		
        //기본 거리를 1로 설정했기 때문에 -1 해서 출력
		cout << dist[x][y] - 1 <<'\n';

	}

	return 0;
}

 

최소 거리를 구하는 문제와 비슷한데 상하좌우를 탐색하는것이 아니라 나이트가 이동할수있는 8곳을 탐색해야 하는것이 다르다.

 

상하좌우로 두칸을 이동해서 양옆에 있는 좌표를 넣어주면 되기때문에

 

int dx[8] = { -2,-2,2,2,-1,1,-1,1 };
int dy[8] = { -1,1,-1,1,-2,-2,2,2 };

 

이렇게 미리 배열을 선언해두고 탐색을 했다.