백준(BOJ) 7562번 나이트의 이동
문제 : https://www.acmicpc.net/problem/7562
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
나의 풀이:
큐에 pair<pair<int,int>,int> 를 통하여 앞에 값에는 y값과 x값을 , 뒤에 값은 이동 횟수로 지정하여 0을 넣고 1씩 증가하여 도착 시 이동 횟수를 저장 하였다.
코드 ( C++ )
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int l;
int x, y, dx, dy;
// 나이트의 이동 방향
int my[8] = { 2,1,-2,-1,-1,-2,1,2 };
int mx[8] = { -1, -2, 1, 2, -2, -1, 2, 1 };
const int MAX = 300;
int chess[MAX][MAX];
bool visited[MAX][MAX];
// 이동 횟수 저장 cnt
int cnt;
void BFS(int y, int x)
{
visited[y][x] = true;
queue<pair<pair<int, int>, int>> q;
// 처음은 y, x 값과 이동 횟수가 0이니 0을 넣어준다.
q.push(make_pair(make_pair(y, x), 0));
while (!q.empty())
{
// q에 다음 나올 y ,x 값이 도착 값과 같다면
if (q.front().first.first == dy && q.front().first.second == dx)
{
// 그때에 이동 횟수를 저장하고 마친다.
cnt = q.front().second;
return;
}
for (int i = 0; i < 8; ++i)
{
int ny = q.front().first.first + my[i];
int nx = q.front().first.second + mx[i];
int num = q.front().second;
if (ny >= 0 && ny < l && nx >= 0 && nx < l)
if (visited[ny][nx] == false)
{
visited[ny][nx] = true;
// num은 다음 칸으로 이동하니 +1 해준다.
q.push(make_pair(make_pair(ny, nx), num + 1));
}
}
q.pop();
}
}
int main()
{
int C;
cin >> C;
while (C--) {
// chess 와 visited 배열 초기화
memset(chess, 0, sizeof(chess));
memset(visited, 0, sizeof(visited));
cnt = 0;
cin >> l;
cin >> y >> x;
cin >> dy >> dx;
BFS(y, x);
cout << cnt << endl;
}
return 0;
}
