알고리즘 :: 백준 :: BFS :: 7562 :: 나이트의 이동

문제

문제접근

문제 이해

• 가장 전형적인 BFS 문제인 2178번: 미로 탐색 (acmicpc.net)와 똑같은 문제입니다.
  다만, 갈 수 있는 방향이 4방향에서 8방향으로 늘었습니다.
• 한 번에 갈 수 있는 칸의 개수가 특정돼있지 않습니다.
  또한, 임의의 칸이 갈 수 있는 여부를 나타내지 않습니다.
  따라서, 체스판의 양사이드에 갈 수 없는 칸을 추가해서 조건문을 줄이는 시도는 여기서 사용하지 않습니다.
• 위 설명을 제외하고는 모든 내용이 알고리즘 :: 백준 :: BFS :: 2178 :: 미로탐색 (velog.io)와 같습니다.

코드

#include <iostream>
#include <cstring>
#include <queue>
#include <tuple>
using namespace std;

bool visited[300][300];
int T, I, d[8][2] = {
    {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, 
    {2, -1}, {1, -2}, {-1, -2}, {-2, -1}
};

bool isValid(int y, int x) {
	return (0 <= y && y < I && 0 <= x && x < I);
}

int solve(int sy, int sx, int ey, int ex) {
	queue<tuple<int, int, int>> q;
	q.push({sy, sx, 0});
	visited[sy][sx] = true;
	while (!q.empty()) {
		int cy, cx, cost; tie(cy, cx, cost) = q.front();
		if (cy == ey && cx == ex) return cost;
		q.pop();
		for (int i = 0; i < 8; ++i) {
			int ny = cy + d[i][0], nx = cx + d[i][1];
			if (isValid(ny, nx) && !visited[ny][nx]) {
				visited[ny][nx] = true;
				q.push({ny, nx, cost + 1});
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
        int sy, sx, ey, ex;
		cin >> I >> sy >> sx >> ey >> ex;
		cout << solve(sy, sx, ey, ex) << '\n';
		memset(visited, false, sizeof(visited));
	}
}

결과