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

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

풀이

시작점에서 목표 지점까지 최소 경로를 구해야 하므로 BFS를 이용했다.

촌수계산 문제와 비슷하게 최소 횟수를 구해야 하므로, 큐에 (노드, 깊이) 쌍을 저장하기 위해서
노드를 좌표 형태(2차원)가 아니라 1차원 배열 형태로 바꿨다.

그리고 현재 나이트가 놓여있는 칸을 노드 A라고 하면, 다음에 이동할 수 있는 8가지 방향 중에서 체스판 안에 포함되는 칸만 A에 연결된 그래프라고 생각하였다.

코드

#include <iostream>
#include <queue>
using namespace std;

int makePos(int x, int y, int m) {
    return x + y * m;
}

vector<int> way(int pos, int l) {
    int x = pos % l;
    int y = pos / l;
    
    vector<int> v;
    int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
    int dy[] = {-1, -2, 2, 1, 1, 2, -2, -1};
    for(int i=0; i<8; i++) {
        int xx = x+dx[i];
        int yy = y+dy[i];
        if(xx >= 0 && xx < l && yy >= 0 && yy < l) {
            v.push_back(makePos(xx, yy, l));
        }
    }
    
    return v;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t, l, cur_x, cur_y, goal_x, goal_y;
    cin >> t;
    
    while(t--) {
        cin >> l >> cur_x >> cur_y >> goal_x >> goal_y;
        
        int ans = 0;
        int cur = makePos(cur_x, cur_y, l);
        int goal = makePos(goal_x, goal_y, l);
        vector<bool> visited(l*l);
        
        queue<pair<int, int>> q;
        q.push({cur, 0});
        visited[cur] = true;
    
        while(!q.empty()) {
            int pos = q.front().first;
            int depth = q.front().second;
            q.pop();
            
            if(pos == goal) {
                ans = depth;
                break;
            }
            
            for(int w : way(pos, l)) {
                if(!visited[w]) {
                    q.push({w, depth+1});
                    visited[w] = true;
                }
            }
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}