나이트의 이동 (feat. 백준, 7562번)

나이트의 이동
https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int dx[8], dy[8], I;
int arr[300][300];
int bfs(register int sx, register int sy, register int ex, register int ey) {
	register int cnt = 0;
	arr[sx][sy] = 1;
	queue<pair<int, int>> q;
	q.push(make_pair(sx, sy));
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		sx = p.first, sy = p.second;
		if (sx == ex && sy == ey) {
			cnt = arr[sx][sy] - 1;
			break;
		}
		for (register int i = 0, nx, ny; i < 8; ++i) {
			nx = sx + dx[i], ny = sy + dy[i];
			if (0 <= nx && nx < I && 0 <= ny && ny < I && !arr[nx][ny])
				arr[nx][ny] = arr[sx][sy] + 1, q.push(make_pair(nx, ny));
		}
	}
	return cnt;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	dx[0] = dx[7] = -2, dx[1] = dx[6] = -1, dx[2] = dx[5] = 1, dx[3] = dx[4] = 2;
	dy[0] = dy[3] = 1, dy[1] = dy[2] = 2, dy[4] = dy[7] = -1, dy[5] = dy[6] = -2;
	register int T;
	cin >> T;
	for (register int t = 0, i, j, sx, sy, ex, ey; t < T; ++t) {
		cin >> I;
		for (i = 0, j; i < I; ++i)
			for (j = 0; j < I; ++j)
				arr[i][j] = 0;
		cin >> sx >> sy >> ex >> ey;
		cout << bfs(sx, sy, ex, ey) << "\n";
	}
	return 0;
}
// *&)*@*

1. 나이트가 이동할 수 있는 방향은 총 8개 입니다.
2. 따라서 이동할때마다 이전 지점에 기록된 값에 +1을 해줍니다.
3. 도착할 지점까지 가면 최소 이동 횟수를 구할 수 있습니다.
4. 최소 이동 횟수와 같은 문제는 이전 '미로 탐색' 처럼 DFS로 풀기에는 비효율적입니다.