Beakjoon 1261 알고스팟

01 Mar 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1261

나의 풀이

부숴야하는 최소한의 벽의 개수를 최단 거리라고 생각하면 이 문제는 (0,0)에서 (N-1, M-1)까지 가는 최단 경로를 찾는 문제와 동일하다.
최단 경로 문제이기 때문에 다익스트라로 접근하였다. 대신 기존에 다루던 1차원적인 값이 아니기 때문에 2차원 배열을 이용해 (0,0)에서부터 각 좌표까지의 최단거리를 구한다.
각 경로에서 이동하는 가중치가 0 또는 1이기 때문에 두 가지 경우를 분리하여 생각하면 문제를 해결할 수 있다.

풀이 코드 : 1261 알고스팟

#include <iostream>
#include <vector>
#include <queue>

#define INF 2000000000

using namespace std;

vector<string> maze;
vector<vector<int>> dist;
vector<vector<int>> visit;

int X[] = {0, 0, 1, -1};
int Y[] = {1, -1, 0, 0};

void dijkstra(){
    int x = 0;
    int y = 0;
    priority_queue<pair<int,pair<int,int>>> pq;
    dist[0][0] = 0;
    pq.push(make_pair(0, make_pair(x,y)));
    while(!pq.empty()){
        x = pq.top().second.first;
        y = pq.top().second.second;
        pq.pop();

        if(visit[y][x] == 1) continue;
        visit[y][x] = 1;
        for(int i=0;i<4;i++){
            int next_x = x + X[i];
            int next_y = y + Y[i];
            if(next_x >=0 && next_x <maze[0].size() && next_y >=0 && next_y < maze.size() && visit[next_y][next_x] == 0){
                if(maze[next_y][next_x] == '1' && dist[next_y][next_x] > dist[y][x] + 1){
                    dist[next_y][next_x] = dist[y][x] + 1;
                    pq.push(make_pair(-dist[next_y][next_x], make_pair(next_x, next_y)));
                }   
                else if(maze[next_y][next_x] == '0' && dist[next_y][next_x] > dist[y][x]){
                    dist[next_y][next_x] = dist[y][x];
                    pq.push(make_pair(-dist[next_y][next_x], make_pair(next_x, next_y)));
                }
            }
        }
        
    }
}
int main(){
    int M, N;
    cin>>M>>N;
    maze.resize(N);
    dist.resize(N);
    visit.resize(N);
    
    for(int i=0;i<N;i++){
        dist[i].resize(M);
        visit[i].resize(M);
        cin>>maze[i];
        for(int j=0;j<M;j++){
            dist[i][j] = INF;
        }
    }
    dijkstra();
    cout<<dist[N-1][M-1];
}

채점결과