[백준] 알고리즘 7562번 - 나이트의 이동문제

문제

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

7562번: 나이트의 이동

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include<memory.h>
#include <stdio.h>
using namespace std;
int l;
int dx[8] = { 1,2,2,1,-1,-2,-1,-2 };
int dy[8] = { 2,1,-1,-2,-2,-1,2,1 };
int check[301][301];
queue<pair<int, int>> qu;
void bfs(int x, int y) {
	qu.push({ x,y });
	check[x][y] = 1;
	while (!qu.empty()) {
		int ox = qu.front().first;
		int oy = qu.front().second;
		qu.pop();
		for (int i = 0; i < 8; i++) {
			int nx = ox + dx[i];
			int ny = oy + dy[i];
			if (nx<0 || nx>l - 1 || ny<0 || ny>l - 1) continue;
			if (check[nx][ny] == 0) {
				check[nx][ny] = check[ox][oy] + 1;
				qu.push({ nx,ny });
			} 
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int x, y, z, k;
		cin >> l >> x >> y >> z >> k;
		bfs(x, y);
		 
		cout << check[z][k]-1<<"\n";
		memset(check, 0, sizeof(check));
	}
}

해설

최소라는 말이 나왔으니 BFS로 우선 해결해보자.

문제만 이해하면 BFS의 틀은 벗어나지 않으니, 문제를 이해하고 조건에 맞는 이동과 조건에 맞는 출력을 해주는게 BFS의 핵심이다.

나이트의 이동은 이전의 문제와 다르게 상하좌우가 아닌 8방향으로 움직이는데, 이 또한 이런식으로 그려보면서 좌표를 설정해주면된다.