백준 7562: 나이트의 이동

문제 요약

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

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

BFS로 풀면 된다.

정사각형의 2차원 배열을 탐색해 나가는데, 단지 탐색 경로가 단순한 상하좌우가 아닌, 나이트의 경로로 바뀐 것 뿐이다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

queue<pair<short, short>> q;
bool visited[1000][1000];
const short dir[8][2] = { {1,2}, {2,1}, {2,-1}, {1,-2},
						{-1,2}, {-2,1}, {-2,-1}, {-1,-2} };

int main()
{
	int t, n, x1, y1, x2, y2, tx, ty, level, qsize;
	bool solve;
	cin >> t;
	while (t--) {
		scanf("%d", &n);
		scanf("%d%d", &x1, &y1);
		scanf("%d%d", &x2, &y2);
		q = queue<pair<short, short>>();
		q.push({ x1, y1 });
		fill_n(&visited[0][0], 1000 * 1000, false);
		visited[y1][x1] = true;
		level = -1;
		solve = false;
		while (!q.empty()) {
			qsize = q.size();
			level++;
			while (qsize--) {
				x1 = q.front().first;
				y1 = q.front().second;
				q.pop();
				if (x1 == x2 && y1 == y2) {
					solve = true;
					break;
				}
				for (int i = 0; i < 8; i++) {
					tx = x1 + dir[i][0];
					ty = y1 + dir[i][1];
					if (tx >= 0 && tx < n && ty >= 0 && ty < n) {
						if (!visited[ty][tx]) {
							q.push({ tx,ty });
							visited[ty][tx] = true;
						}
					}
				}
			}
			if (solve) break;
		}
		printf("%d\n", level);
	}
	return 0;
}