[Baekjoon] [7562 : 나이트의 이동] C++ 풀이

나이트의 이동 문제는 BFS로 최소 이동 수를 찾는 문제이고 이동하는데 걸리는 횟수를 dist에 저장하면서

bfs를 돌리면 간단하게 풀립니다.

 

 

풀이

---

#include <bits/stdc++.h>
using namespace std;

int dx[8] = {-1, -1, -2, -2, 1, 1, 2, 2};
int dy[8] = {-2, 2, -1, 1, -2, 2, -1, 1};
// 나이트의 이동 경로


int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, l;
	cin >> n; //테스트 케이스 입력

	while (n--)
	{
		cin >> l;

		queue<pair<int, int>> q; //bfs를 위한 queue
		int dist[301][301]; //distance를 저장하는 이차원 배열
		for (int i=0; i<l; i++)
			fill(dist[i], dist[i] + l, -1); //dist를 -1로 초기화

		int sx, sy;
		int ex, ey;
		cin >> sx >> sy; //start x, y
		q.push({sx, sy}); // queue에 넣고
		dist[sx][sy] = 0; //방문을 표시

		cin >> ex >> ey; //end x, y
		
		while(!q.empty()) //bfs 시작
		{
			auto cur = q.front(); q.pop(); 
			bool check = false; //bfs를 종료해야 하는지 check
			if (cur.first == ex && cur.second == ey) //시작점과 종점이 같으면 예외처리
			{
				cout << "0\n";
				break;
			}
			for (int i=0; i<8; i++)
			{
				int nx = cur.first + dx[i];
				int ny = cur.second + dy[i];

				if (nx < 0 || nx >= l || ny < 0 || ny >= l) //인덱스를 벗어날 경우
					continue;
				if (dist[nx][ny] >= 0) //이미 방문했을 경우
					continue;
				if (nx == ex && ny == ey) // 종점에 다다르면
				{
					cout << dist[cur.first][cur.second]  + 1<< "\n"; //출력
					check = true; //bfs를 종료
					break;
				}
				q.push({nx, ny});
				dist[nx][ny] = dist[cur.first][cur.second] + 1;
			}
			if (check)
				break;
		}
	}
	return 0;
}