문제링크: https://www.acmicpc.net/problem/7562

문제

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

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

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

출력

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

풀이

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

bool visited[300][300];

std::pair<int, int> start;
std::pair<int, int> end;

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

void bfs(int a, int b, int size) {
	visited[a][b] = true;

	// pair -> <<x, y> pair, time>
	std::queue<std::pair<std::pair<int, int>, int>> q;
	q.push(std::make_pair(std::make_pair(a, b), 0));

	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int time = q.front().second;
		q.pop();

		if (x == end.first && y == end.second) {
			std::cout << time << "\n";
			return;
		}
		else {
			for (int i = 0; i < 8; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx < 0 || nx >= size || ny < 0 || ny >= size) {
					continue;
				}
				else if (!visited[nx][ny]) {
					visited[nx][ny] = true;

					q.push(std::make_pair(std::make_pair(nx, ny), time + 1));
				}
			}
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cout.tie(NULL);
	std::cin.tie(NULL);

	int T; std::cin >> T;

	for (int tc = 0; tc < T; tc++) {
		memset(visited, 0, sizeof(visited));

		int l; std::cin >> l;

		std::cin >> start.first >> start.second;
		std::cin >> end.first >> end.second;

		bfs(start.first, start.second, l);
	}

	return 0;
}

dfs로 풀고싶었지만 방법이 떠오르지 않았다.
변수를 입력받고 bfs내에서 queue에 시간을 넣는 부분이 조금 까다로웠다.
queue에 x, y좌표를 넣으면서 동시에 시간을 넣고 bfs로 돌려야했다.
그리고 엄청나게 애를 먹은 부분이 바로 queue에 push를 해줄 때였다.
nx, ny에 방문 한 것을 update하지 않으면 무한루프에 빠졌다.
그 이외의 다른 어려운 점은 없이 순서대로 진행만 하면 구현 가능한 문제였다.

노트

dfs연습을 하고자 했는데, bfs로 풀게됐다. bfs도 공부해야하니 좋은 기회였다.
dfs, bfs를 할 때는 visited 조건을 잘 생각하는 연습이 더 중요할 것 같다.