7562 나이트의 이동 (C++)

 

BFS로 풀면되는 문제였다.

 

그.. 근데 조금 다른거라면, 종료되는 조건이 있다라는 것이다. 보통의 BFS 문제들은 미로통과하기, 다 채워질때의 최솟값 등을 물어보는데, 이건 목적지가 정해져 있고, 나이트가 그 지점으로 이동했을 경우의 수를 리턴하는 문제였다.

 

구조는 기존의 BFS 문제와 같다. 조건문만 추가 해주고 리턴할 수 있게 해주면 된다.

(함수로 나누지 않았다. 일단 구현이 먼저라고 생각해서.. 나중에 시간이 된다면 나누는 작업을 진행하겠다.

 

코드에 나오는 X,Y 는 pair의 기능인 first, second 의 단축어이다. #define으로 설정해놨으니 헷갈리지 말길 바란다.

 

그리고 pair에 추가하는 x,y 좌표는 솔직히 x를 먼저 추가하든 y를 먼저 추가하든 상관없는 것 같다. 일단 내가 참고한 코에서는 저렇게 하고 있어서 일단 그렇게 했다. (정사각형이라 그런거지 가로 세로의 길이가 다른 문제는 꼭 y,x 순서를 잘 지정해 놔야한다.

 

사실 처음 시도에는 cnt 변수를 선언해서 돌때마다 카운트 되게 했었다. 지금 정답 코드의 기능과 다른게 없다고 생각하는데, 막상 해보면 결과는 다르게 나오니..그 쪽을 수정하고 제출해보았다.

 

그리고 memset을 하나만 사용했었다. dist에만 사용하고 board에는 for문을 돌렸었는데, 그것또한 에러의 요인이었던것 같다.

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[300][300];
bool dist[300][300];
int dy[8] = {2,1,-2,-1,-1,-2,1,2};
int dx[8] = {-1,-2,1,2,-2,-1,2,1};
int t,n;
int night_x, night_y, target_x, target_y;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while(t--) {
		cin >> n;
		memset(board,0,sizeof(board));
		memset(dist, false, sizeof(dist));
		cin >> night_y >> night_x;
		cin >> target_y >> target_x;
		
		queue<pair<pair<int,int>,int>> Q;
		Q.push({{night_y,night_x},0});
		dist[night_y][night_x] = true;
		
		while(!Q.empty()) {
			auto cur = Q.front();
			
			if(cur.X.X == target_y && cur.X.Y == target_x) {
				cout << Q.front().Y << '\n';
				break;
			}
			
			for(int dir = 0; dir < 8; ++dir) {
				int nx = cur.X.Y + dx[dir];
				int ny = cur.X.X + dy[dir];
				int num = cur.Y;
				if(nx >= 0 && nx < n && ny >= 0 && ny < n) {
					if(dist[ny][nx] == false) {
						dist[ny][nx] = true;
						Q.push({{ny,nx}, num+1});
						
					}
				}
			}
			Q.pop();
		}
		
	}
}