BOJ 16509 · 장군

알고리즘 분류 : BFS  

장기 말을 옮기는 최소 횟수를 구하는 문제다. BFS를 통해 상(象)을 옮겨서 왕을 먹어야 한다.

• 장기판에서 상을 옮겨서 왕의 위치로 도달하는 최소 횟수를 구해야 한다.
• 상은 그림처럼 움직이며, 움직이는 경로에 다른 말이 있으면 해당 위치로 옮길 수 없다. 다른 말은 존재하지 않기 때문에, 왕의 위치가 상의 이동 경로에 있는지만 고려하면 된다.
• 별도로 이동 좌표를 만들고, 움직이는 경로에 왕이 있다면 상을 움직이지 않는다.
• 이동이 가능하다면 옮긴다.

---

C++ 소스코드

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

struct grid {
    int x, y;
};

int sx, sy, ex, ey;
int dist[10][9];
const int dx[8][3] = {
    {-1, -2, -3}, {-1, -2, -3}, {0, -1, -2}, {0, -1, -2},
    {0, 1, 2}, {0, 1, 2}, {1, 2, 3}, {1, 2, 3} };
const int dy[8][3] = {
    {0, -1, -2}, {0, 1, 2}, {-1, -2, -3}, {1, 2, 3},
    {-1, -2, -3}, {1, 2, 3}, {0, -1, -2}, {0, 1, 2} };

bool move(int i, int &x, int &y) {
    int nx = x, ny = y;
    for (int j=0; j<3; j++) {
        nx = x+dx[i][j], ny = y+dy[i][j];
        if (nx < 0 || nx >= 10 || ny < 0 || ny >= 9) return false;
        if (j < 2 && nx == ex && ny == ey) return false;
    }
    x = nx, y = ny;
    return true;
}

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

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

---

Python 3 소스코드

from collections import deque
sx, sy = map(int, input().split())
ex, ey = map(int, input().split())
dist = [[-1]*9 for _ in range(10)]
dx = [(-1, -2, -3), (-1, -2, -3), (0, -1, -2), (0, -1, -2),
      (0, 1, 2), (0, 1, 2), (1, 2, 3), (1, 2, 3)]
dy = [(0, -1, -2), (0, 1, 2), (-1, -2, -3), (1, 2, 3),
      (-1, -2, -3), (1, 2, 3), (0, -1, -2), (0, 1, 2)]

def move(i, x, y):
    nx, ny = x, y
    for j in range(3):
        nx, ny = x+dx[i][j], y+dy[i][j]
        if nx < 0 or nx >= 10 or ny < 0 or ny >= 9:
            return -1, -1
        if j < 2 and nx == ex and ny == ey:
            return -1, -1
    return nx, ny

def bfs():
    q = deque()
    q.append((sx, sy))
    dist[sx][sy] = 0
    while q:
        x, y = q.popleft()
        if x == ex and y == ey:
            print(dist[x][y])
            return
        for i in range(8):
            nx, ny = move(i, x, y)
            if nx != -1 and dist[nx][ny] == -1:
                q.append((nx, ny))
                dist[nx][ny] = dist[x][y]+1
    print(-1)

bfs()

---

참고

• 백준 온라인 저지 : BOJ 16509