<Baekjoon> #16948 BFS_Death Knight c++

(r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구하는 문제이므로 BFS를 이용해 풀어야 한다는 것을 알 수 있다.
(대개 BFS는 그래프에서의 최단 경로 문제를 푸는데 용도로 사용된다)

1. BFS 복습
   

2. queue <pair<int, int>> q
queue에는 r,c 좌표 한 쌍이 들어가야 하므로 pair로 선언해주고 처음에는 현재 위치 r,c를 넣어준다

	queue <pair<int, int>> q;
	q.push(make_pair(r, c));

3. r,c 가 움직일 수 있는 방향

int dy[6] = { -2,-2,0,0,2,2 };
int dx[6] = { -1,1,-2,2,-1,1 };

• 현재 위치 cur_y, cur_x에서 움직일 수 있는 6개 위치를 구해준다

		for (int i = 0; i < 6; i++) 
			int nx_y = cur_y + dy[i];
			int nx_x = cur_x + dx[i];

• 구해진 위치 (nx_y, nx_x)가 체스 판의 범위를 넘지 않고, 한 번도 발견되지 않았으면 즉,dis[nx_y][nx_x]=-1이면 현재 거리 dist[cur_y][cur_x]에 1을 더해준다

			if (nx_y<0 || nx_x<0 || nx_y>n || nx_x>n) continue;
			if (dist[nx_y][nx_x] == -1) {
				q.push(make_pair(nx_y, nx_x));
				dist[nx_y][nx_x] = dist[cur_y][cur_x] + 1;}

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
const int MAX = 201;
int dist[MAX][MAX];
int dy[6] = { -2,-2,0,0,2,2 };
int dx[6] = { -1,1,-2,2,-1,1 };
int n;

void bfs(int r, int c) {
	dist[r][c] = 0;
	queue <pair<int, int>> q;
	q.push(make_pair(r, c));

	while (!q.empty()) {
		int cur_y = q.front().first;
		int cur_x = q.front().second;
		q.pop();

		for (int i = 0; i < 6; i++) {
			int nx_y = cur_y + dy[i];
			int nx_x = cur_x + dx[i];

			if (nx_y<0 || nx_x<0 || nx_y>n || nx_x>n) continue;
			if (dist[nx_y][nx_x] == -1) {
				q.push(make_pair(nx_y, nx_x));
				dist[nx_y][nx_x] = dist[cur_y][cur_x] + 1;
			}
		}
	}
 }
int main() {
	memset(dist, -1, sizeof(dist));
	cin >> n;
	int r1, r2, c1, c2;
	cin >> r1 >> c1 >> r2 >> c2;
	bfs(r1, c1);
	cout << dist[r2][c2] << endl;
	return 0;
}