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

 

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

7562번: 나이트의 이동

#문제 간단 정리

 

체스판 위에서 나이트가 이동하는 최소 횟수를 계산하는 문제를 해결하기 위한 코드입니다. 코드는 입력으로 주어지는 테스트 케이스를 처리하고, 각 테스트 케이스에 대해 나이트가 최소 몇 번 움직여야 하는지를 출력합니다. 코드는 너비 우선 탐색(BFS)을 사용하여 문제를 해결합니다

 

#전체 코드

#include <iostream>
#include <queue>

using namespace std;

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

struct point {
	int x, y;
};

int main() {


	int N; cin >> N;
	while (N--) {
		int I;
		cin >> I;
		point now, target;
		cin >> now.x >> now.y >> target.x >> target.y;

		if (now.x == target.x && now.y == target.y) {
			cout << '0' << endl;
			continue;
		}

		int chessBoard[300][300] = { 0, };

		queue<point> q;
		q.push(now);
		chessBoard[q.front().x][q.front().y] = 0;

		while (!q.empty()) {
			int x = q.front().x;
			int y = q.front().y;
			q.pop();
			for (int i = 0; i < 8; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (0 <= nx && nx < I && 0 <= ny && ny < I) {
					if (chessBoard[nx][ny] == 0) {
						q.push({ nx,ny });
						chessBoard[nx][ny] = chessBoard[x][y] + 1;
					}
				}

			}
		}

		cout << chessBoard[target.x][target.y]<< endl;

		
	}






	return 0;
}

 

 

#문제 해결 방법

해당 문제는 나이트의 이동을 최소한의 움직임으로 목표 위치까지 가는 최단 거리를 찾는 문제입니다. 이를 위해 BFS(Breadth-First Search)를 사용합니다.

문제 해설:

1. 나이트의 이동
   나이트는 8가지 방향으로 움직일 수 있습니다. 문제에서 제시한 그림을 참고하면, 나이트의 모든 움직임을 (dx, dy)의 형태로 나타낼 수 있습니다.
2. BFS
   BFS는 시작 지점부터 가장 가까운 지점들부터 차례대로 탐색하는 알고리즘입니다. 체스판에서의 나이트 이동도 이 알고리즘으로 효율적으로 해결할 수 있습니다. BFS를 사용하면, 각 칸에 도달하는 데 필요한 최소한의 움직임 횟수를 찾을 수 있습니다.

코드 설명:

• 변수
  • dx, dy: 나이트의 이동 방향을 저장한 배열입니다.
  • point: x, y 좌표를 갖는 구조체입니다.
  • chessBoard: 각 위치에 도달하기 위한 최소 움직임 횟수를 저장하는 체스판입니다.
• 프로세스
  1. 테스트 케이스의 수를 입력 받습니다.
  2. 각 테스트 케이스마다
     • 체스판의 크기, 시작 위치, 목표 위치를 입력 받습니다.
     • 시작 위치와 목표 위치가 같다면, 움직일 필요가 없으므로 0을 출력하고 다음 테스트 케이스로 넘어갑니다.
     • 그렇지 않다면, BFS로 최단 거리를 찾습니다.
     • BFS를 진행하며, 체스판에 각 칸까지 도달하기 위한 최소 움직임 횟수를 저장합니다.
     • 목표 위치까지의 최소 움직임 횟수를 출력합니다.

BFS를 사용하여 문제를 해결하면, 체스판의 각 칸까지 도달하는 데 필요한 최소 움직임 횟수를 효율적으로 찾을 수 있습니다.