BOJ 1261 · 알고스팟

알고리즘 분류 : BFS, 다익스트라  

2178번 미로탐색에서 약간 변형된 문제이다. (1, 1)부터 (N, M)까지 미로를 이동하면서 벽을 부시는 최소 횟수를 구해야 한다.

• 빈 방으로 이동하면 가중치가 0, 벽으로 이동하면 가중치가 1인 것으로 바꿔서 생각한다.
• 가중치가 0과 1로 나뉘므로, 일반적인 BFS 방법으로는 풀 수 없다.
• 이를 BFS 방법으로 해결하기 위해 큐(Queue)를 2개 사용하면 된다.
• 빈 방으로 이동할 때는 첫 번째 큐에 넣고, 벽을 부수고 이동할 때는 두 번째 큐에 넣는다.
• 두 개의 큐에 들어간 값을 순서대로 빼면서 처리하면 된다.
• 큐를 2개 사용하므로, 덱(Deque)을 앞 뒤로 사용하면 비슷한 방법으로 해결할 수 있다.

---

C++ 소스코드

#include <cstdio>
#include <deque>
using namespace std;

struct maze {
    int x, y;
};

int m, n;
int a[101][101];
int dist[101][101];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int bfs() {
    deque<maze> dq;
    dq.push_back({1, 1});
    a[1][1] = -1;
    while (!dq.empty()) {
        int x = dq.back().x, y = dq.back().y;
        dq.pop_back();
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (a[nx][ny] == -1) continue;
            else if (a[nx][ny] == 0) {
                // Empty room (0)
                dq.push_back({nx, ny});
                dist[nx][ny] = dist[x][y];
            } else {
                // Wall (1)
                dq.push_front({nx, ny});
                dist[nx][ny] = dist[x][y] + 1; // Count broken walls
            }
            a[nx][ny] = -1; // Visited (-1)
        }
    }
    return dist[n][m];
}

int main() {
    scanf("%d %d", &m, &n);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            scanf("%1d", &a[i][j]);
        }
    }
    printf("%d\n", bfs());
    return 0;
}

✓ 가중치가 있는 그래프에서 1:N 최단 거리를 구하는 문제와 같으므로, 다익스트라 알고리즘으로도 구현할 수 있다.

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

struct maze {
    int x, y, d; // x, y is position, d is distance.
    bool operator < (const maze t) const { return d > t.d; }
};

int m, n;
int a[101][101];
int dist[101][101];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int INF = 1e9;

int dijkstra() {
    priority_queue<maze> pq; // Min heap
    pq.push({1, 1, 0});
    dist[1][1] = 0;
    while (!pq.empty()) {
        int x = pq.top().x, y = pq.top().y, d = pq.top().d;
        pq.pop();
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            int nd = d + a[nx][ny];
            if (dist[nx][ny] > nd) {
                dist[nx][ny] = nd;  // Update distance, if minimum.
                pq.push({nx, ny, nd});
            }
        }
    }
    return dist[n][m];
}

int main() {
    scanf("%d %d", &m, &n);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            scanf("%1d", &a[i][j]);
            dist[i][j] = INF;
        }
    }
    printf("%d\n", dijkstra());
    return 0;
}

---

Python 3 소스코드

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

m, n = map(int, input().split())
a = [list(map(int, list(input().strip()))) for _ in range(n)]
d = [[0]*m for _ in range(n)]
dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

def bfs():
    dq = deque()
    dq.append((0, 0))
    a[0][0] = -1
    while dq:
        x, y = dq.pop()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if a[nx][ny] == -1:
                continue
            elif a[nx][ny] == 0:
                d[nx][ny] = d[x][y]
                dq.append((nx, ny))
            else:
                d[nx][ny] = d[x][y] + 1
                dq.appendleft((nx, ny))
            a[nx][ny] = -1
    return d[n-1][m-1]

print(bfs())

from sys import stdin
from heapq import heappush, heappop
input = stdin.readline

m, n = map(int, input().split())
a = [list(map(int, list(input().strip()))) for _ in range(n)]
dist = [[1e9] * m for _ in range(n)]
dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

def dijkstra():
    pq = []
    heappush(pq, (0, 0, 0))
    dist[0][0] = 0
    while pq:
        d, x, y = heappop(pq)
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            nd = d + a[nx][ny]
            if dist[nx][ny] > nd:
                dist[nx][ny] = nd
                heappush(pq, (nd, nx, ny))
    return dist[n-1][m-1]

print(dijkstra())

---

참고

• 백준 온라인 저지 : BOJ 1261
• 위키피디아 : 다익스트라 알고리즘
• 미로 탐색