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

출처 :7562번: 나이트의 이동 (acmicpc.net)

7562번: 나이트의 이동

풀이 방법

문제에서 몇 번 만에 갈 수 있는지 구하라 했으므로 bfs를 사용하여 풀이하였다

다른 보편적인 문제(상하 좌우 이동)와 다른 점은 나이트의 이동 경로가 8가지로 다르게 정해져 있었다.

이동 경로를 dy, dx에 저장해 두고 이용하였다.

#include <bits/stdc++.h>
using namespace std ;

int visited[301][301];
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int c, l,start_x, start_y, last_x, last_y;
//bfs
int solve() {
    queue<pair<int, int>> q;
    q.push(make_pair(start_x, start_y));
    visited[start_x][start_y] = 0;
    while(!q.empty()) {
        int xx = q.front().first;
        int yy = q.front().second;
        q.pop();
        for (int i = 0;i < 8;i++) {
            int nx = xx + dx[i];
            int ny = yy + dy[i];
            if (nx >= 0 && ny >= 0 && nx < l && ny < l && visited[nx][ny] == -1) {
                if (nx == last_x && ny == last_y) {
                    return visited[xx][yy] + 1;
                }
                q.push(make_pair(nx, ny));
                visited[nx][ny] = visited[xx][yy] + 1;
            }
        }
    }
    return 0;
}
int main () {
    cin >> c;
    for (int i = 0;i < c;i++) {
        memset(visited, -1, sizeof(visited));
        cin >> l;
        cin >> start_x >> start_y;
        cin >> last_x >> last_y;
        int ans = solve();
        cout << ans <<endl;
    }
}