[백준#C++] 데스 나이트

문제

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

접근 과정

1. 일반적으로 상하좌우 대신 나이트의 이동을 dy, dx에 저장 후 BFS를 통해 거리를 계산

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int n;
int r1, c1, r2, c2;

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

int dist[205][205];

void input() {
	scanf("%d",&n);

	scanf("%d%d%d%d",&r1, &c1, &r2, &c2);
}

void BFS() {
	memset(dist, -1, sizeof(dist));

	int sy = r1;
	int sx = c1;

	dist[sy][sx] = 0;
	queue < pair<int, int>> q;
	q.push(make_pair(sy, sx));

	while (1) {
		if (q.empty()) break;
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 6; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
		
			if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
				if (dist[ny][nx] == -1) {
					q.push(make_pair(ny, nx));
					dist[ny][nx] = dist[y][x] + 1;
				}
			}
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	input();

	BFS();

	printf("%d", dist[r2][c2]);

	return 0;
}

느낀점

• 일반적인 BFS 문제였다.