알고리즘/BFS, DFS
[C++] 백준 7562번 나이트의 이동
키베이루
2022. 6. 10. 08:20
1) 문제설명
https://www.acmicpc.net/problem/7562
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
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;
}
}
}