취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 7562번 문제인 나이트의 이동이다.
문제는 아래 링크를 확인하자.

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

주어지는 체스판은 많아봐야 90000칸으로, 그 칸수가 매우 적다.

BFS를 이용해 시작 칸에서 각 체스판의 칸까지 나이트가 이동해야하는 횟수를 구하고, 도착지의 거리를 출력해주자.

나이트의 8방향의 움직임을 아래 코드와 같이 dr배열과 dc배열에 기록해두면 구현을 편하게 할 수 있다.

아래는 제출한 소스코드이다.

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

int L, sR, sC, eR, eC;
int arr[300][300];
int dr[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int dc[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };

void bfs() {
	arr[sR][sC] = 1;
	queue<pair<int, int>> que;
	que.push(make_pair(sR, sC));
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second;
		que.pop();
		for (int i = 0; i < 8; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= L || cc < 0 || cc >= L) continue;
			if (arr[rr][cc]) continue;
			arr[rr][cc] = arr[r][c] + 1;
			que.push(make_pair(rr, cc));
		}
	}
}

void solve() {
	memset(arr, 0, sizeof(arr));
	cin >> L >> sR >> sC >> eR >> eC;
	bfs();
	cout << arr[eR][eC] - 1 << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) solve();
}