BOJ 12273 · Dragon Maze (Large)

알고리즘 분류 : BFS  

드래곤이 파워를 모으면서 탈출하는 것을 구현하는 문제다. BFS를 통해 맵을 탐색하면서 구하면 된다. 비슷한 문제로 BOJ 12272번 'Dragon Maze (Small)'이 있다. Small 문제는 Large 문제보다 범위만 적은 것이므로, 같은 코드로 해결 가능하다.

• 입구에서 출구까지 최단 거리로 이동해야 한다. 단, 정답은 이동하면서 얻은 파워 합의 최댓값이다.
• 따라서 일반적인 큐(Queue)를 쓰는 것보다, 우선순위 큐(Priority Queue)를 이용하는 것이 좋다.
• 이동 거리가 짧을수록, 파워 합이 클수록 우선순위가 높도록 처리한다. 우선순위 큐에 (이동거리, 파워, X 좌표, Y 좌표) 순으로 넣는다.
• 맵을 탐색하면서 위험지역(-1)을 제외한 곳으로 이동한다. 이동한 곳의 파워를 합산한다.

---

C++ 소스코드

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

int n, m, sx, sy, ex, ey;
int a[100][100];
bool check[100][100];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int bfs() {
    priority_queue<tuple<int, int, int, int>> q;
    q.push(make_tuple(0, a[sx][sy], sx, sy));
    while (!q.empty()) {
        auto t = q.top(); q.pop();
        int dist = -get<0>(t), power = get<1>(t);
        int x = get<2>(t), y = get<3>(t);
        if (x == ex && y == ey) return power;
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (!check[nx][ny] && a[nx][ny] >= 0) {
                q.push(make_tuple(-dist-1, power+a[nx][ny], nx, ny));
                check[nx][ny] = true;
            }
        }
    }
    return -1;
}

int main() {
    int T;
    scanf("%d", &T);
    for (int t=1; t<=T; t++) {
        memset(check, 0, sizeof(check));
        scanf("%d %d", &n, &m);
        scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        printf("Case #%d: ", t);
        int k = bfs();
        if (k >= 0) printf("%d\n", k);
        else printf("Mission Impossible.\n");
    }
    return 0;
}

✓ C++의 Priority queue는 Max Heap이므로, 거리 값을 음수로 처리해야 한다.

---

Python 3 소스코드

from heapq import heappush, heappop

def bfs():
    q = []
    heappush(q, (0, -a[sx][sy], sx, sy))
    while q:
        dist, power, x, y = heappop(q)
        if x == ex and y == ey:
            return -power
        for dx, dy in (-1,0), (1,0), (0,-1), (0,1):
            nx, ny = x+dx, y+dy
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if not check[nx][ny] and a[nx][ny] >= 0:
                heappush(q, (dist+1, power-a[nx][ny], nx, ny))
                check[nx][ny] = True
    return -1

for t in range(int(input())):
    n, m = map(int, input().split())
    sx, sy, ex, ey = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    check = [[False]*m for _ in range(n)]
    print("Case #%d:" % (t+1), end=' ')
    k = bfs()
    if k >= 0:
        print(k)
    else:
        print("Mission Impossible.")

✓ Python의 Heapq는 Min Heap이므로, 파워 합을 음수로 처리해야 한다.

---

참고

• 백준 온라인 저지 : BOJ 12273
• 백준 온라인 저지 : BOJ 12272