[백준 / C언어] 7562번: 나이트의 이동 (BFS 풀이)

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

7562번: 나이트의 이동

 

난이도: solved.ac 실버 1

 

알고리즘 분류

---

그래프 탐색 (BFS)

 

접근 방법

---

최소 이동 횟수를 구하는 문제이므로 BFS로 접근하였다.

 

구현

---

위의 그림처럼 1시 방향부터 시작해 11시 방향까지 시계 방향으로 이동시키는 것을 한 단계로 큐에 넣어주었다.

방문한 좌표는 visited에 몇 번째로 이동한 건지 적어주었다.

 

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#define MAX 300

typedef struct _Queue {
	int y;
	int x;
} Queue;

Queue q[MAX * MAX + 1];
int visited[MAX][MAX];
int dy[8] = { -2,-1,1,2,2,1,-1,-2 };
int dx[8] = { 1,2,2,1,-1,-2,-2,-1 };
int front, rear;

void BFS(int py, int px, int desy, int desx, int I);

int main() {
	int T, I, i;
	int py, px, desy, desx;
	scanf("%d", &T);
	while (T) {
		scanf("%d", &I);
		scanf("%d %d", &py, &px);
		scanf("%d %d", &desy, &desx);

		BFS(py, px, desy, desx, I);
		printf("%d\n", visited[desy][desx]);

		for (i = 0; i < I; i++)
			memset(visited[i], 0, sizeof(int) * I);
		T--;
	}
	return 0;
}

void BFS(int py, int px, int desy, int desx, int I) {
	front = 0; rear = 0;
	q[rear].y = py;
	q[rear].x = px;
	visited[py][px] = 0;
	while (q[front].y != desy || q[front].x != desx) {
		int order = visited[q[front].y][q[front].x];
		for (int dir = 0; dir < 8; dir++) {
			int ny = q[front].y + dy[dir];
			int nx = q[front].x + dx[dir];
			if (ny >= 0 && ny < I && nx >= 0 && nx < I) {
				if (!visited[ny][nx]) {
					rear++;
					q[rear].y = ny;
					q[rear].x = nx;
					visited[ny][nx] = order + 1;
				}
			}
		}
		front++;
	}
}