백준 #1261 알고스팟

3 minute read

백준 #1261 알고스팟

벽과 빈 공간으로 이루어진 공간에서, (1, 1)에서 (N, M)까지 최소 몇 개의 벽을 뚫고 갈 수 있는지를 계산하는 문제. 다익스트라를 활용하면 풀 수 있다.

1
1
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
0
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
Cost: 1
Cost: 1
Viewer does not support full SVG 1.1

입력을 모두 2차원 배열에 저장한다. 2차원 배열의 원소는 그래프의 정점에 해당하고, 원소와 원소 사이를 간선으로 생각한다. 이때, 1이 저장된 정점으로 가는 간선의 cost를 1로, 0이 저장된 정점으로 가는 간선의 cost를 0으로 설정한다. 이렇게 벽을 부수는 행위를 간선의 cost로 나타내면 다익스트라 알고리즘으로 가장 적은 비용, 즉 (N, M)까지 도달하는 데에 가장 적게 부수는 벽의 개수를 구할 수 있다.

#include <iostream>
#include <memory.h>
#include <queue>
#include <tuple>
#include <vector>
#define INF 1e9

using namespace std;

int N, M;
vector<tuple<int, int, int>> graph[100][100];
int board[100][100];
int dist[100][100];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0,};


bool isInBoard(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < M;
}

void dijkstra() {
    for(int i = 0; i < 100; i++) {
        fill(dist[i], dist[i] + 100, INF);
    }
    dist[0][0] = 0;
    priority_queue<tuple<int, int ,int>> q;
    q.push({-dist[0][0], 0, 0});
    while(!q.empty()) {
        int hereX = get<1>(q.top());
        int hereY = get<2>(q.top());
        q.pop();
        for(int i = 0; i < graph[hereX][hereY].size(); i++) {
            int nextX = get<0>(graph[hereX][hereY][i]);
            int nextY = get<1>(graph[hereX][hereY][i]);
            int nextCost = get<2>(graph[hereX][hereY][i]);
            if(dist[nextX][nextY] > dist[hereX][hereY] + nextCost) {
                dist[nextX][nextY] = dist[hereX][hereY] + nextCost;
                q.push({-dist[nextX][nextY], nextX, nextY});
            }
        }
    }
}

int main() {
    cin >> M >> N;
    getchar();
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            board[i][j] = getchar() - '0';
        }
        getchar();
    }


    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            for(int k = 0; k < 4; k++) {
                int nX = i + dx[k];
                int nY = j + dy[k];
                if(isInBoard(nX, nY)) {
                    graph[i][j].push_back({nX, nY, board[nX][nY]});
                }
            }
        }
    }

    dijkstra();
    cout << dist[N - 1][M - 1];
    return 0;
}

이 문제는 0-1 BFS 방식으로도 풀 수 있다. 간선의 가중치가 모두 0 또는 1이니, 다익스트라보다 0-1 BFS 방식으로 푸는 것이 더 효율적이다. 0-1 BFS는 다익스트라와 비슷하지만, 우선순위 큐가 아닌 덱을 사용해 가중치가 0일 때는 앞에 push하고 1일 때는 뒤에 push하는 방식이다.

#include <iostream>
#include <memory.h>
#include <deque>
#include <tuple>
#include <vector>
#define INF 1e9

using namespace std;

int N, M;
vector<tuple<int, int, int>> graph[100][100];
int board[100][100];
int dist[100][100];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0,};


bool isInBoard(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < M;
}

void bfs() {
    for(int i = 0; i < 100; i++) {
        fill(dist[i], dist[i] + 100, INF);
    }
    dist[0][0] = 0;
    deque<pair<int, int>> deq;
    deq.push_back({0, 0});
    while(!deq.empty()) {
        int hereX = deq.front().first;
        int hereY = deq.front().second;
        deq.pop_front();
        for(int i = 0; i < graph[hereX][hereY].size(); i++) {
            int nextX = get<0>(graph[hereX][hereY][i]);
            int nextY = get<1>(graph[hereX][hereY][i]);
            int nextCost = get<2>(graph[hereX][hereY][i]);
            if(dist[nextX][nextY] > dist[hereX][hereY] + nextCost) {
                dist[nextX][nextY] = dist[hereX][hereY] + nextCost;
                if (nextCost) {
                    deq.push_back({nextX, nextY});
                } else {
                    deq.push_front({nextX, nextY});
                }
            }
        }
    }
}

int main() {
    cin >> M >> N;
    getchar();
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            board[i][j] = getchar() - '0';
        }
        getchar();
    }


    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            for(int k = 0; k < 4; k++) {
                int nX = i + dx[k];
                int nY = j + dy[k];
                if(isInBoard(nX, nY)) {
                    graph[i][j].push_back({nX, nY, board[nX][nY]});
                }
            }
        }
    }

    bfs();
    cout << dist[N - 1][M - 1];
    return 0;
}

Comments