BOJ 7562 · 나이트의 이동

알고리즘 분류 : BFS  

나이트의 최단 이동 거리를 구하는 문제다. 전형적인 BFS 문제이며, 나이트 이동에 해당하는 이동 좌표만 잘 설정하면 된다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct chess {
    int x, y;
};

int n, sx, sy, ex, ey;
int d[300][300];
const int dx[] = {2, 1, -1, -2, -2, -1, 1, 2};
const int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

void bfs() {
    queue<chess> q;
    q.push({sx, sy});
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        if (x == ex && y == ey) {
            printf("%d\n", d[x][y]);
            return;
        }
        for (int i=0; i<8; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (d[nx][ny]) continue;
            d[nx][ny] = d[x][y] + 1;
            q.push({nx, ny});
        }
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        scanf("%d %d", &sx, &sy);
        scanf("%d %d", &ex, &ey);
        memset(d, 0, sizeof(d));
        bfs();
    }
    return 0;
}

---

Python 3 소스코드

from sys import stdin
from collections import deque
input = stdin.readline

dx = (2, 1, -1, -2, -2, -1, 1, 2)
dy = (1, 2, 2, 1, -1, -2, -2, -1)

def bfs():
    q = deque()
    q.append((sx, sy))
    while q:
        x, y = q.popleft()
        if x == ex and y == ey:
            print(d[x][y])
            return
        for i in range(8):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if not d[nx][ny]:
                d[nx][ny] = d[x][y] + 1
                q.append((nx, ny))

for _ in range(int(input())):
    n = int(input())
    sx, sy = map(int, input().split())
    ex, ey = map(int, input().split())
    d = [[0]*n for _ in range(n)]
    bfs()

---

참고

• 백준 온라인 저지 : BOJ 7562