백준 7562 나이트의 이동(c++)

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

7562번: 나이트의 이동

<코드>

#include <iostream>
#include <cstring>
#include <queue>
#define max 301
using namespace std;
queue<pair<int,int>>q;
int board[max][max];
bool visited[max][max];
int mov [8][2] = {{2,1},{1,2},{-2,1},{-1,2},{-2,-1},{-1,-2},{1,-2},{2,-1}}; // 말의 이동 
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		memset(board,0,sizeof(board));
		memset(visited,0,sizeof(visited));
		int l;
		cin>>l;
		int startx,starty;
		cin>>startx>>starty;
		q.push({startx,starty});
		visited[startx][starty] = true;
		int endx,endy;
		cin>>endx>>endy;
		while(!q.empty()){
			pair<int,int> xy = q.front();
			q.pop();
			if(xy.first == endx && xy.second == endy) {
				cout<<board[xy.first][xy.second]<<'\n';
				while(!q.empty()){
					q.pop();
				}
				break;
			}
			for(int i=0;i<8;i++){
				int sr = xy.first + mov[i][0];
				int sc = xy.second + mov[i][1];
				if(sr<0 || sc<0 || sr>l-1 || sc>l-1 ) continue;
				if(visited[sr][sc] ) continue;
				if(!visited[sr][sc])
				{
					q.push({sr,sc});
					visited[sr][sc] = true;
					board[sr][sc] = board[xy.first][xy.second]+1;
				}
			}
		
		}	
	}
}

<풀이과정>

bfs를 활용한 기본 문제이다. 나이트가 이동할 수 있는 좌표들을 각각 배열에 저장해두고, 시작점으로부터 좌표를 이동해 도착점까지 갈 때 까지 개수를 하나씩 추가해주면 끝이다.