[백준] 20046번 Road Reconstruction c++

https://www.acmicpc.net/problem/20046

문제

홍수의 발생으로 인해 도시의 도로들이 유실되어 많은 ICP(International Computational Plan) 시민들이 불편을 겪고 있다. 도시는 아래와 같은 격자 형태로 표현이 된다고 가정하자. 검정색 단위 격자가 ‘단위도로’를 의미하며 흰색 단위 격자는 도로가 없었거나 유실된 상태를 의미한다. X로 표시된 단위 격자는 도로를 건설할 수 없는 곳을 의미한다.

도시의 차들은 단위 도로 상에서 가로나 세로 방향으로만 움직인다고 가정했을 때 도시의 기능을 회복시키기 위해 맨 왼쪽 위 단위 격자에서 맨 오른쪽 아래 단위 격자로 도시의 차들이 가는 경로를 만들기 위해 필요한 최소한의 도로 건설 비용을 계산하고자 한다. 단위 도로 하나를 건설하기 위해 1 또는 2 의 비용이 소요된다고 가정하자. 위 그림에서는 흰색 단위 격자에 단위 도로 하나를 건설하기 위해서는 1 의 비용이 든다고 가정한다.

위와 같이 회색으로 표시된 단위 도로들을 4 의 비용으로 건설하면 목적을 달성할 수 있다.

도시가 위와 같이 격자 형태로 주어졌을 때 맨 왼쪽 위 단위 격자에서 맨 오른쪽 아래 단위 격자로 가는 경로를 만들기 위해 필요한 최소 도로 건설 비용을 구하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각 열의 정보를 나타내는 n개의 숫자가 주어진다. 각 열의 정보는 정수 0, 1, 2, -1 로 나타내며 0 은 단위도로가 이미 존재하는 것을, 즉, 도로에 유실이 없는 상태, 1 은 단위 도로가 없고 1 의 비용으로 도로를 건설할 수 있는 단위 격자, 2 는 단위 도로가 없고 2 의 비용으로 도로를 건설할 수 있는 단위 격자를 의미한다. -1 은 X로 표시된 단위 격자로 그 위치에 단위 도로를 건설할 수 없는 상태를 의미한다.

출력

출력은 표준출력을 사용한다. 도시의 맨 왼쪽 위 단위 격자에서 맨 오른쪽 아래 단위 격자로 가는 경로를 만들기 위해 필요한 최소한의 도로 건설 비용을 한 줄에 출력한다. 해당 경로를 건설할 수 없을 때는 -1 을 출력한다.

 

문제접근 및 풀이

- BFS와 다익스트라 알고리즘을 응용하여 해결하였다.

- 우선순위 큐를 사용하여 비용이 가장 낮은 경로를 우선적으로 탐색하도록 했다.

- 따라서 탐색중 (n-1,m-1)에 처음 도달한 순간의 cost가 답이된다.

- 탐색을 실패하고 큐가 비게되면 가능한 경로가 없는 것으로 -1을 출력한다.

#include <iostream>
#include <queue>
#define MAX 1000

using namespace std;

int n,m;
int b[MAX][MAX];

struct P{
    int x;
    int y;
    int c;
};

struct cmp{
    bool operator()(P a, P b){
        return a.c > b.c; // 작은 것부터 빼야하므로 오름차순정렬 즉 앞이 커 클때 반환
    }
};

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int bfs(){
    int v[MAX][MAX]={0};
    priority_queue<P, vector<P>, cmp> pq;
    
    int start = b[0][0];
    if(start==-1) return -1;
    if(start==0) pq.push({0,0,0});
    if(start==1) pq.push({0,0,1});
    if(start==2) pq.push({0,0,2});
    v[0][0]=1;
    
    while(!pq.empty()){
        P p = pq.top();
        int x = p.x;
        int y = p.y;
        int c = p.c;
        pq.pop();
        //printf("x:%d, y:%d, c:%d\n",x,y,c);
        if(x==n-1 && y==m-1){
            return c;
        }
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && ny >= 0 && nx < n && ny < m){
                int k = b[nx][ny];
                if(v[nx][ny]==0 && b[nx][ny]!=-1){ // 방문안했고 다리 못놓는 자리가 아니라면 건설 or 경유
                    v[nx][ny]=1; // v[nx][ny]==1; 로 했더니 방문체크가 안되서 계속 돌고도는 현상 발생
                    if(k==0){
                        pq.push({nx,ny,c});
                    }
                    if(k==1){
                        pq.push({nx,ny,c+1});
                    }
                    if(k==2){
                        pq.push({nx,ny,c+2});
                    }
                }
                
            }
        }
    }
    return -1;
}

int main()
{
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d", &b[i][j]);
        }
    }
    cout << bfs();
    return 0;
}

 

느낀점

시간복잡도를 보아하니 bfs단순 탐색만으로는 시간초과가 날것같아서, priority queue를 바로 떠올려 해결한점이 뿌듯하다. 다른 코드를 찾아보니 단순 bfs 탐색을 한경우 시간초과가 났다고 한다.