나이트의 이동 //7562

• 문제
  
  
  // 시간 제한: 1초, 메모리 제한: 256MB

• 입력
  입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
  각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

• 출력
  각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

// Created by dongwan-kim on 2022/08/22.
#include<iostream>
#include<algorithm>
#include<queue>

#define MAX 301
using namespace std;

int t, n, a, b, c, d, graph[MAX][MAX], ans;
bool visit[MAX][MAX];

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

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    visit[x][y] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < n && ny < n && graph[nx][ny] == 0 && !visit[nx][ny]) {
                graph[nx][ny] = graph[x][y] + 1;
                visit[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n;		//체스판의 크기
        cin >> a >> b;	//나이트가 현재 있는 좌표
        cin >> c >> d;	//나이트가 이동하려고 하는 좌표

        bfs(a, b);

        cout << graph[c][d] << "\n";

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = 0;
                visit[i][j] = false;
            }
        }

    }
}

풀이

나이트가 최소 몇 번 움직여야 해당 칸으로 이동할 수 있는지 알아봐야하기 때문에
BFS를 사용해 문제를 해결했다.

대부분의 그래프 2차원 문제에서는 dx,dy배열을 사용해서 푸는 문제는 "위,아래,왼쪽,오른쪽" 이동으로 만들었지만 이 문제는 나이트의 이동이므로 8개 선언하여 움직여 주었다.

처음 나이트의 위치를 (a,b) 입력받고 bfs를 a,b부터 돌린다. BFS가 다 돌고나면 graph배열 각각 인덱스에 나이트가 해당 좌표로 이동하기 위해서 몇번 움직였는지가 담기게 된다. 따라서 나이트의 이동하려는 최종 좌표를 c,d에 입력 받아놓고 마지막에 graph[c][d]를 출력해 주면 된다.

테스트 케이스만큼 위와 같은 과정을 반복하기 때문에 마지막에 visit,graph배열을 초기화 해주어야 한다.