[백준 7562] 나이트의 이동

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

---

해설

 

일단, 그림만 봐도 BFS 라는 것을 짐작할 수있다.

색칠 된 부분의 좌표를 두 배열에 저장해놓고 BFS를 돌리면 풀 수있다.

 

현재 내 좌표를 0, 0으로 가정하고 나머지 색칠 된 부분의 좌표를 시계 방향으로 적어보겠다.

 

int di[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dj[8] = {1, 2, 2, 1, -1, -2, -2, -1};

 

이 좌표를 가지고 현재 x와 y가 갈 수있는 좌표와 움직인 횟수를 큐에 넣어주고 업데이트 하면서 x와 y가 목적지에 도착하면 while을 빠져나와 count 한 값을 출력해주면 된다.

 

 

˙˙˙

소스코드

 

#include <iostream>
#include <queue>
using namespace std;
int di[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dj[8] = {1, 2, 2, 1, -1, -2, -2, -1};
bool visited[300][300];

int main(){
	int t; cin >> t;
	for(int ii=0; ii<t; ii++){
		int l; cin >>l;
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		queue<pair<int, pair<int, int> > > q;
		q.push({ a, {b, 0} });
		for(int i=0; i<300; i++)
			for(int j=0; j<300; j++)
				visited[i][j] = false;
		visited[a][b] = true;
		while(!q.empty()){
			pair<int, pair<int, int> > F = q.front();
			q.pop();
			if(F.first == c && F.second.first == d){
				cout << F.second.second << '\n';
				break;
			}
			for(int e=0; e<8; e++){
				int ni = F.first + di[e];
				int nj = F.second.first + dj[e];
				if(ni>=0 && ni < l && nj >=0 && nj < l){
					if(!visited[ni][nj]){
						q.push({ni, {nj, F.second.second+1}});
						visited[ni][nj] = true;
					}
				}
			}
		} 
	}
}