[알고리즘/문제풀이][BOJ 7562번] 나이트의 이동

나이트의 이동 문제는 BFS를 사용하여 해결할 수 있는 문제입니다. BFS로 나이트가 이동 가능한 모든 노드들을 탐색하여 목표하는 노드까지의 최단거리를 계산할 수 있습니다. 나이트의 특이한 이동 조건을 잘 고려하기만 하면 문제를 쉽게 풀 수 있습니다.

작성한 코드는 다음과 같습니다.

#include<stdio.h>
#pragma warning(disable : 4996)
//https://ark-hive.tistory.com/

int T;
int I;
int board[330][330];
int current[2];
int target[2];
int dx[8] = { 1, 1, 2, 2, -1, -1,-2,-2 };
int dy[8] = { 2, -2, 1, -1, 2, -2, -1, 1 };

struct que {
	int x, y, time;
};

struct que queue[300 * 300];

int wp, rp;

void enqueue(int x, int y, int time) {
	queue[wp].x = x;
	queue[wp].y = y;
	queue[wp].time = time;
	wp++;
	return;
}

struct que dequeue() {
	return queue[rp++];
}

int empty() {
	return rp == wp;
}

void BFS() {
	wp = 0, rp = 0;
	board[current[1]][current[0]] = 1;
	enqueue(current[0], current[1], 0);

	while (!empty()) {
		struct que temp = dequeue();
		if (temp.x == target[0] && temp.y == target[1]) {
			printf("%d\n", temp.time);
			return;
		}
		for (int i = 0; i < 8; i++) {
			int nx = temp.x + dx[i];
			int ny = temp.y + dy[i];
			if (nx < 0 || nx >= I) continue;
			if (ny < 0 || ny >= I) continue;
			if (board[ny][nx] == 1) continue;
			board[ny][nx] = 1;
			enqueue(nx, ny, temp.time + 1);
		}
	}
}

int main(void) {
	scanf("%d", &T);

	for (int i = 0; i < T; i++) {
		scanf("%d", &I);
		for (int j = 0; j < I; j++) {
			for (int k = 0; k < I; k++) {
				board[j][k] = 0;
			}
		}
		scanf("%d %d", &current[0], &current[1]);
		scanf("%d %d", &target[0], &target[1]);
		BFS();
	}
}

문제의 링크는 다음과 같습니다.

acmicpc.net/problem/7562