[백준 7562] 나이트의 이동 (C++)

이 문제는 나이트를 처음 위치에서 목표 위치로 이동시킬 때, 몇 번 이동해야하는지 계산하는 문제이다.

가장 단순한 방법은 처음부터 가능한 모든 경우를 따져보는 것이다.

이 문제에서는 나이트의 이동방법으로 고정되어 있기 때문에, 모든 경우를 따질 때 얼마만큼의 시간이 걸릴지 직관적인 파악이 힘들다.

이럴 경우, 모든 경우의 수를 따져보고 시간초과가 발생하면, 다른 풀이법을 고안하는 것이 옳다고 본다.

다시 문제 풀이로 돌아와보자.

나이트처럼 이동하기 때문에, BFS나 DFS로 접근하는 것이 다음 위치를 계산하는데 용이할 것이다. 또한, 최단 거리를 구해야하므로 BFS로 접근하는 것이 적절해보인다.

이제 코드를 짜보자.

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int tc, l;
pair<int, int> current, target;
int vis[300][300];
int dx[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int dy[] = { 2, 1, -1, -2, 2, 1, -1, -2 };

int solve() {
    if (current == target) return 0;
    
    queue<pair<int, int>> q;
    q.push(current);
    vis[current.X][current.Y] = 0;
    
    while (!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();
        
        for (int dir = 0; dir < 8; dir++) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= l || ny < 0 || ny >= l) continue;
            if (vis[nx][ny] != -1) continue;
            if (make_pair(nx, ny) == target) return vis[x][y] + 1;
            q.push({nx, ny});
            vis[nx][ny] = vis[x][y] + 1;
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> tc;
    while (tc--) {
        cin >> l >> current.X >> current.Y >> target.X >> target.Y;
        for (int i = 0; i < l; i++) fill(vis[i], vis[i] + l, -1);
        cout << solve() << "\n";
    }
}

먼저, 모든 테스트케이스마다 로직을 반복해야하므로, 이를 별도의 함수로 추출하였다.

시작점과 목표점이 동일하면 0을 출력, 그렇지 않으면 이동 횟수를 출력해야한다.
이를 위해서, current와 target이 동일한지 전처리를 하고, bfs를 진행하였다.