[백준] 7562 나이트의 이동

문제 설명

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

7562번: 나이트의 이동

체스판 위에 한 나이트가 놓여져있고, 나이트가 한 번에 이동할 수 있는 칸이 주어졌을 때 나이트는 몇 번 움직이면 해당 칸으로 이동할 수 있을지 구하기

 

문제 풀이법

최단 거리를 찾는 문제이므로 bfs를 사용하여 문제를 풀 수 있다

 

백준 1697번 숨바꼭질과 비슷한 문제로, 1차원인 숨바꼭질 문제와 달리 2차원인것만 다르다

 

우선 나이트는 움질일 수 있는 범위가 다음과 같다

• (-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)

 

나이트가 움직인 횟수를 담는 배열 arr를 선언하고 -1로 초기화해준다

큐가 빌때까지 while문을 도는 기존 bfs문제와 달리 이번 문제는 해당 위치에 값이 들어오면 while문을 종료하게 된다

큐에는 나이트가 현재 있는 칸을 시작점으로 넣어두고, 이동 횟수를 갱신하면서 while문을 돌리게 된다

 

while문이 종료되면 해당 칸에 있는 값을 출력하면 된다

 

소스 코드

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int t, n;

int x, y, x2, y2;

int arr[301][301];

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

int main()
{
    cin >> t;
    
    while (t--)
    {
        cin >> n;
        cin >> x >> y;
        cin >> x2 >> y2;
    
        for (int i = 0; i < n; i++)
            fill(arr[i], arr[i] + n, -1);
            
        queue<pair<int, int>> q;
        q.push({y, x});
        
        arr[y][x] = 0;
        
        while (arr[y2][x2] == -1)
        {
            int yy = q.front().first;
            int xx = q.front().second;
            
            q.pop(); 
            
            for (int i = 0; i < 8; i++)
            {
                int ny = yy + dy[i];
                int nx = xx + dx[i];
                
                if (ny < 0 || nx < 0 || ny >= n || nx >= n)
                    continue;
                if (arr[ny][nx] != -1)
                    continue;
                arr[ny][nx] = arr[yy][xx] + 1;
                q.push({ny, nx});
            }
        }
        printf("%d\n", arr[y2][x2]);
    }
    return 0;
}