백준(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;

}