백준 7562번: 나이트의 이동 (C++)

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

7562번: 나이트의 이동

 

나이트가 현재 위치에서 특정 위치로 이동할 때, 이동 횟수를 구하는 것이다.

 

나이트가 한번 움직일 때 이동 거리가 1이라고 생각한다면, 최단거리를 구하는 문제로 이해할 수 있다

 

따라서 bfs로 접근하되, 나이트의 움직임을 표현해주면 되겠다.

 

 

새로운 위치가 큐에 삽입될 때, 추가되는 위치가 목적지인지 비교하고, 만약 목적지라면 bfs를 끝낸다.

 

보통의 bfs는 큐가 빌 때 종료되는데, 이번 문제는 그렇지 않다.

 

따라서 여러 개의 테스트 케이스를 처리할 때 다른 변수들과 마찬가지로 큐 또한 비워주는 것이 중요하다.

 

#include<iostream>
#include<queue>
using namespace std;
int n, dist[301][301];
queue<pair<int, int> >q;
int dr[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int dc[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
void bfs(pair<int, int> Src, pair<int, int> Dst) {
	q.push(Src);
	dist[Src.first][Src.second]++;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		for (int i = 0; i < 8; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			
			if (nr < 0 || nc < 0 || nr >= n || nc >= n || dist[nr][nc] >= 0) continue;
			
			q.push({ nr, nc });
			dist[nr][nc] = dist[cur.first][cur.second] + 1;
			if (nr == Dst.first && nc == Dst.second) return; //이후에 큐 비우기
		}
	}
}
int main(void) {
	int tc;
	cin >> tc;
	while (tc--) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dist[i][j] = -1;
			}
		}
		pair<int, int> src, dst;
		cin >> src.first >> src.second >> dst.first >> dst.second;
		bfs(src, dst);

		cout << dist[dst.first][dst.second] << '\n';
		
		//초기화
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dist[i][j] = -1;
			}
		}
		while (!q.empty()) q.pop(); //queue가 비워지지 않은 상태로 bfs가 끝난다
	}
	return 0;
}