[백준 2665 - C++] 미로만들기 : 다익스트라(Dijkstra)

www.acmicpc.net/problem/2665

2665번: 미로만들기

문제

n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.

시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

아래 그림은 n=8인 경우의 한 예이다.

위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면, 시작방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.

단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.

 

입력

첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

 

출력

첫 줄에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력한다.

 

 

풀이

이 문제는 DFS나 BFS로 풀어도 될듯하지만 나는 우선순위큐로 구현한 다익스트라 알고리즘으로 풀이하였다.

흰방의 경우엔 비용을 0으로, 검은 방의 경우엔 비용을 1로 하여 실행하면 다익스트라 알고리즘의 실행이 종료될 때 cost[n-1][n-1]에 든 값이 지나가야하는 검은방의 최소수가 된다.

상하좌우로 움직이는 경우에 map바깥으로 나가는지 잘 확인을 해주어야한다. 

 

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

using namespace std;
char map[50][50];
int cost[50][50];
int X[4] = {1, -1, 0, 0};
int Y[4] = {0, 0, 1, -1};
priority_queue<pair<int, pair<int, int>>> pq; //변경수, x, y

int main(void){
    
    int n;
    int x, y, cnt;
    int next_x, next_y, next_cnt;
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%s",map[i]);
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cost[i][j]= -1;
        }
    }
    
    pq.push(make_pair(0, make_pair(0, 0)));
    cost[0][0] = 0;
    while(!pq.empty()){
        cnt = -pq.top().first;
        x = pq.top().second.first;
        y = pq.top().second.second;
        pq.pop();
        
        if(cost[x][y] < cnt)
            continue;
        
        for(int i=0; i<4; i++){
            next_x = x + X[i];
            next_y = y+ Y[i];
            if(next_x < 0 || next_x >= n|| next_y < 0 || next_y >=n){
                continue;
            }
            if(map[next_x][next_y] == '0'){ //검
                next_cnt = cnt+1;
            }
            else{   //흰
                next_cnt = cnt;
            }
            
            if(cost[next_x][next_y] ==-1){
                cost[next_x][next_y] = next_cnt;
                pq.push(make_pair(-next_cnt, make_pair(next_x, next_y)));
            }
            else if(cost[next_x][next_y] > next_cnt){
                cost[next_x][next_y] = next_cnt;
                pq.push(make_pair(-next_cnt, make_pair(next_x, next_y)));
            }
        }
    }
    printf("%d\n", cost[n-1][n-1]);
    
}