[BOJ 1261 // C++] 알고스팟

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1261번 문제인 알고스팟이다.
문제는 아래 링크를 확인하자.

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

1261번: 알고스팟

이 문제는 배열로 표현된 미로의 좌상단에서 우하단까지 벽을 최소 몇번 뚫어야 갈 수 있는가를 구하는 문제이다.

이 문제는 다익스트라(Dijkstra) 알고리즘으로 해결할 수 있다.

 

미로의 각 칸을 노드로 생각하고, 벽이 있는 칸을 향하는 방향의 간선(edge)의 가중치를 1, 빈 방을 향하는 방향의 간선의 가중치를 0으로 생각하자.

이렇게 생각한 그래프는 음의 가중치가 없는 방향그래프이므로, 이 그래프의 좌상단 방에서 우하단 방으로 가는 최단경로를 찾아 나오는 숫자가 곧 벽을 뚫은 횟수가 된다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using std::cin;
using std::cout;
using std::vector;
using std::pair;
using std::priority_queue;
using std::string;

string maze[101];
int dist[101][101];
bool done[101][101];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

priority_queue<pair<int, pair<int,int>>> pq;

int main()
{
    int r, c;
    cin >> c >> r;
    for (int i = 1;i <= r;i++) {
        string x;
        cin >> x;
        maze[i] = ' ' + x; // 첫 방의 열번호를 1로 만들기 위함
    }
    for (int i = 1;i <= r;i++) {
        for (int j = 1;j <= c;j++) {
            dist[i][j] = 1000;
        }
    }
    dist[1][1] = 0;
    pq.push({ 0,{ 1,1 } });
    while (!pq.empty()) { // Dijkstra
        pair<int, pair<int,int>> current = pq.top(); pq.pop();
        int f = current.second.first, s = current.second.second;
        if (done[f][s]) continue;
        else if (f == r and s == c) break;
        done[f][s] = true;
        for (int i = 0;i < 4;i++) {
            int x = f + dr[i], y = s + dc[i];
            if (0 < x and x <= r and 0 < y and y <= c) {
                if (dist[x][y] > dist[f][s] + (maze[x][y] - '0')) { // char -> int 변환
                    dist[x][y] = dist[f][s] + (maze[x][y] - '0');
                    pq.push({ -dist[x][y],{x,y} });
                }
            }
        }
    }
    cout << dist[r][c];

    return 0;
}