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

문제 링크:https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

<문제 풀이> BFS

기본적인 BFS 최단거리 문제랑 똑같은데 방향만 8방향으로 설정해주면 됩니다.

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

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first
#define Y second
 
int dx[8] = {-2, -1, 1, 2, -2, -1, 1, 2};
int dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int visited[300][300];
 
int bfs(int n, int cx, int cy, int wx, int wy) {
    queue<pair<int, int> > Q;
    Q.push({ cx, cy });
    visited[cx][cy] = 0;
    if (cx == wx && cy == wy) return visited[wx][wy];
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        cx = cur.X;
        cy = cur.Y;
        for (int dir = 0; dir < 8; dir++) {
            int nx = cx + dx[dir];
            int ny = cy + dy[dir];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if (visited[nx][ny] != -1) continue;
            Q.push({ nx, ny });
            visited[nx][ny] = visited[cx][cy] + 1;
            if (nx == wx && ny == wy) return visited[wx][wy];
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_case; cin >> test_case;
    while (test_case--) {
        int n; cin >> n;
        int cx, cy; cin >> cx >> cy;
        int wx, wy; cin >> wx >> wy;
        fill(&visited[0][0], &visited[299][300], -1);
        cout << bfs(n, cx, cy, wx, wy)<<'\n';
    }
  
    return 0;
}