[BOJ] 백준 7562번 나이트의 이동

링크

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

문제

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

입력

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

출력

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

풀이

 #include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <tuple>

using namespace std;
#define X first
#define Y second
int l, tc; 

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

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//상하좌우 탐색이 아니라 나이트의 탐색이다. 총 여덟방향
	//그리고 전체를 탐색하거나 끝날때까지 탐색하는게 아니라 특정칸을 탐색하는 최솟값인데
	//bfs 성질상 가장 맨첨에 탐색한 거리가 최소 거리다. 큐에 거리순으로 담기기 때문이다.
	cin >> tc;
	while (tc--) {
		queue <pair <int, int>> q;
		//dist 초기화
		cin >> l;
		for (int i = 0; i < l; i++)
			fill(dist[i], dist[i] + l, -1);
		bool findAns = false;
		int x, y, targetX, targetY; 
		cin >> x >> y >> targetX >> targetY;
		dist[x][y] = 0; 
		q.push({ x, y });
		while (!q.empty()) { // bfs
			pair <int, int > cur = q.front();
			q.pop();
			if (cur.X == targetX && cur.Y == targetY) {
				cout << dist[cur.X][cur.Y] << '\n';
				continue;
			}
			for (int i = 0; i < 8; i++) {
				int nx = cur.X + dx[i];
				int ny = cur.Y + dy[i];
				if (nx < 0 || nx >= l || ny < 0 || ny >= l) continue; 
				if (dist[nx][ny] != -1) continue;
				if (nx == targetX && ny == targetY) {
					findAns = true;
					break;
				}
				dist[nx][ny] = dist[cur.X][cur.Y] + 1;
				q.push({ nx, ny });
			}
			if (findAns == true) {
				cout << dist[cur.X][cur.Y] + 1 << '\n';
				break;
			}

		}

	}

}

설명

• 상하좌우 탐색이 아니라 나이트의 탐색이다. 총 여덟방향 dx[8] dy[8]
• 전체를 탐색하거나 끝날때까지 탐색하는게 아니라 특정칸에 대한 거리 최솟값인데 ⭐ bfs 성질상 가장 맨첨에 탐색한 거리가 최소 거리다. 큐에 거리순으로 담기기 때문이다.
• board배열은 필요없다.