백준 7562번 C++

백준 7562번 나이트의 이동

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

7562번: 나이트의 이동

정답 코드

#include<iostream>
#include<queue>
using namespace std;
int vis[305][305]; //횟수를 기록하는 배열
int dx[8] = { -2,-2,-1,-1,1,1,2,2 };
int dy[8] = { 1,-1,2,-2,2,-2,1,-1 };
queue<pair<int, int>>q;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int test;
	cin >> test;
	for (int i = 0; i < test; i++) {
		int len, x, y, x_final, y_final;
		cin >> len;
		cin >> x >> y;
		cin >> x_final >> y_final;
		if (x == x_final && y == y_final) {
			cout << '0' << '\n';
			continue;
		}
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++)
				vis[i][j] = -1;
		}
		vis[x][y] = 0;
		q.push({ x,y });
		while (!q.empty()) {
			pair<int, int>cur = q.front();
			q.pop();
			for (int d = 0; d < 8; d++) {
				int mx = cur.first + dx[d];
				int my = cur.second + dy[d];
				if (mx < 0 || my < 0 || mx >= len || my >= len)
					continue;
				if (vis[mx][my] >= 0)
					continue;
				vis[mx][my] = vis[cur.first][cur.second] + 1;
				q.push({ mx,my });

			}
		}
		cout << vis[x_final][y_final] << "\n";
	}
}

문제 풀이

bfs를 이용해서 풀었습니다. 먼저 vis배열을 -1로 초기화시켰습니다. 그 다음 입력받은 좌표를 큐에 집어넣고 이 좌표를 기점으로 bfs를 돌렸습니다. 움직일 수 있는 방향은 8개이므로 dx,dy배열을 8칸씩 만들었습니다.
범위를 벗어나거나 이미 방문한 곳은 continue하도록 설정하였고 이 두 가지의 경우가 아닐 때에는 큐에 좌표를 집어넣고
vis[mx][my] = vis[cur.first][cur.second] + 1;
를 통해 이동 횟수를 더해주었습니다.