[2665번][C/C++] 미로만들기

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

2665번: 미로만들기

하얀 방(1)과 검은 방(0)으로 구성된 1*1 크기의 방들이 n*n크기의 맵을 이루고 있다.

이때, (1, 1)에서 (n, n)까지 가고 싶은데 검은 방은 지나갈 수 없으므로 하얀 방으로 색을 바꾸고 지나가야 한다.

이때 검은 방의 색을 최소한의 횟수로 바꾸고 (n, n)에 도달하려면 몇 번 바꿀 수 있는지 알아보는 문제이다.

 

얼핏 보면 벽 부수고 지나가기 시리즈를 생각할 수 있는 문제이다.

하지만 그래프에 대한 내공이 있다면 최단거리 문제, 0-1 BFS 문제를 떠올릴 수 있다.

 

이 문제가 벽 부수기 시리즈와 다른 점은 하얀 방을 지나가는 횟수는 신경 쓰지 않는다는 것이다.

이 말을 그래프로 해석해보면 하얀 방으로 가는 것은 가중치가 0인 간선을 지나는 것과 같다는 것이다.

그리고 검은방으로 가는 것은 가중치가 1인 간선을 지나는 것과 같다.

 

따라서 우리는 가중치가 0과 1의 간선으로 구성된 그래프에서 (1, 1)노드에서 (n, n)노드로의 최단거리를 구하면 그 값은 즉 가장 조금 검은방의 색을 하얀 방으로 바꾼 횟수를 의미한다.

 

따라서 입력받을 때 하얀 방의 가중치는 0, 검은 방으로의 가중치는 1로 구성해서 그래프를 만든 뒤, (1, 1)에서 다익스트라나 BFS를 사용하면 답을 구할 수 있다.

 

나는 다익스트라 구현이 더 편해서 다익스트라로 구현했다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>

#define INF 987654321

using namespace std;

int graph[52][52];
int dist[52][52];
int direc[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int n;

bool isIn(int y, int x) {
    if(1 <= y && y <= n && 1 <= x && x <= n) return true;
    else return false;
}

void dijkstra(int sy, int sx) {
    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push({0, {sy, sx}});

    while(!pq.empty()) {
        pair<int,int> cur = pq.top().second;
        int cCost = -pq.top().first;
        pq.pop();

        for(int i=0;i<4;i++) {
            pair<int,int> next = {cur.first + direc[i][0], cur.second + direc[i][1]};
            int nCost = graph[next.first][next.second];

            if (isIn(next.first, next.second) && dist[next.first][next.second] > cCost + nCost) {
                dist[next.first][next.second] = cCost + nCost;
                pq.push({-dist[next.first][next.second], next});
            }
        }
    }
}

void init() {
    for(int i=0;i<52;i++) {
        for(int j=0;j<52;j++) {
            dist[i][j] = INF;
        }
    }
}

int main() {
    init();

    scanf("%d", &n);
    for(int i=1;i<=n;i++) {
        getchar();
        for(int j=1;j<=n;j++) {
            char inp;
            scanf("%c", &inp);
            if(inp == '1') graph[i][j] = 0;
            else graph[i][j] = 1;
        }
    }

    dijkstra(1, 1);

    printf("%d", dist[n][n]);

    return 0;
}