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

 

1) 문제설명

백준 Online Judge 7562번 나이트의 이동

백준 Online Judge 7562번 나이트의 이동.

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

7562번: 나이트의 이동

 

2) 아이디어

나이트의 최소 이동 횟수를 구해야 하기 때문에 bfs를 사용한다.

나이트의 이동 규칙은 (1,2) (1,-2) (2,1) (2,-1) (-1,2) (-1,-2) (-2,1) (-2,-1) 이므로 그에 따른 배열을 만든다.

이에 따라 BFS탐색을 한다면 쉽게 나이트의 최소 이동 횟수를 구할 수 있다.

※ 여러 번의 테스트 케이스를 구해야 하기 때문에 memset을 사용하여 배열을 다시 초기화시켜주어야 한다.

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int arr[301][301] = { 0, };
int range[301][301] = { 0, };
int result;
int dfs(int x, int y, int tx, int ty, int n) {
	queue <pair<int,int>> q;
	
	memset(arr, 0, sizeof(arr)); // 배열 초기화
	memset(range, 0, sizeof(range));

	q.push(make_pair(x, y));
	arr[x][y] = -1; // 처음방문
	
	int dx[] = { 1,1, 2,2,-1,-1,-2,-2 };
	int dy[] = { 2,-2,1,-1,2,-2,1,-1 };



	while (!q.empty()) {

		x = q.front().first;
		y = q.front().second;
		
		q.pop();
		if (x == tx && y == ty) {
			break;
		}
		for (int i = 0; i < 8; i++) {
			int nx, ny;
			nx = x + dx[i];
			ny = y + dy[i];
			if (nx >= n || ny >= n || nx < 0 || ny < 0 || arr[nx][ny] == -1) { // 범위를 벗어나거나 방문한 곳이면
				continue; // 넘어간다
			}
			else {
				
				arr[nx][ny] = -1;
				q.push(make_pair(nx, ny)); // 1 2 , 2 1
				range[nx][ny] = range[x][y] + 1; // r[1][2] = 0 + 1, r[2][1] = 0 + 1
				result = range[nx][ny]; // 1

				if (nx == tx && ny == ty) { // 다음좌표와 목표좌표가 같다면
					return result; // 리턴
				}
			}
		}
		
	}
}
int main() {
	int t, n, sx, sy, tx, ty;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		cin >> sx >> sy >> tx >> ty;
		if (sx == tx && sy == ty) {
			cout << 0 << endl;
		}
		else {
			cout << dfs(sx, sy, tx, ty, n) << endl;
		}
	}
}