[백준] 7562번 C++ 나이트의 이동

나이트의 이동 문제로 대표적인 그래프 탐색 문제이다.

bfs를 이용하여 풀었으며, 정답률이 높기때문에 이 문제를 입문으로 그래프문제를 풀면 좋을 것 같다.

 

 

풀이)

#include<iostream>
#include<queue>
#include<vector>
#include<array>
using namespace std;

const int MAX = 301;
int len;
int cnt{};
int dx[8] = { 1,2,2,1,-1,-2,-2,-1 };
int dy[8] = { 2,1,-1,-2,-2,-1,1,2 };
/* 방문했는지 확인할 visited 
*  bfs 돌릴 queue	
*  가중치 계산할 map
*/

int visited[MAX][MAX]{ {} };
int map[MAX][MAX]{ {} };


void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push({ x,y });
	visited[y][x] = 1;

	while (not q.empty()) {
		int a = q.front().first;
		int b = q.front().second;
		q.pop();

		for (int i = 0; i < 8; ++i) {
			int nx = a + dx[i];
			int ny = b + dy[i];
			
			if (0 <= nx && nx < len && 0 <= ny && ny < len && not visited[ny][nx] && map[ny][nx] == 1) {
				q.push({nx,ny});
				visited[ny][nx] = visited[b][a] + 1;
			}			
		}		
	}

}


int main()
{
	int t;
	cin >> t;

	while (t--) {
		int  x, y, x2, y2;
		cin >> len;
		cin >> x >> y >> x2 >> y2;
		
		//배열 초기화
		cnt = 0;
		for (int i = 0; i < len; ++i) {
			for (int j = 0; j < len; ++j) {
				map[i][j] = 1;
				visited[i][j] = 0;
			}
		}

		bfs(x, y);
		
		cout << visited[y2][x2] - 1 << '\n';

	}


}