백준[1261] - 알고스팟

문제

백준 1261 문제 보기

접근 방법

문제의 정답은 벽을 최소로 부수면서 도착지에 도착하게끔 구현해야한다.

bfs로도 풀수 있을 것 같긴하나 시간 초과가 발생할 수도 있을것 같다. 따라서 다익스트라 알고리즘을 사용했다.

벽을 부수는 갯수를 해당 좌표까지 이동하는 비용으로 생각하고 문제를 풀었다.

코드

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int r, c;
int map[101][101];
int broken[101][101];
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

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

int main() {
    cin >> c >> r;
    // 벽을 부순 갯수를 나타내는 broken 지도
    memset(broken, -1, sizeof(broken));

    for(int i = 0; i < r; i ++) {
        for(int j = 0; j < c; j ++) {
            // 숫자 하나씩 입력 받으며 map에 그림
            scanf(" %1d", &map[i][j]);
        }
    }

    // 우선 순위 큐에 {벽을 부순 숫자, {좌표1, 좌표2}}
    // 즉, (좌표1, 좌표2)까지 이동하기 위해 부순 벽돌수를 저장
    pq.push({0, {0, 0}});

    while(!pq.empty()) {
        int broken_cnt = -pq.top().first;
        int rr = pq.top().second.first;
        int cc = pq.top().second.second;
        pq.pop();

        // 이미 해당 경로를 통과했을 경우
        if(broken[rr][cc] != -1) {
            continue;
        }

        // 부순 벽돌 수 저장
        broken[rr][cc] = broken_cnt;

        // 위, 오른쪽, 아래, 왼쪽
        for(int i = 0; i < 4; i ++) {
            int nr = rr + dr[i];
            int nc = cc + dc[i];

            // 범위 안에 존재하고
            if(nr >= 0 && nc >= 0 && nr < r && nc < c) {
                // 다음 목적지를 방문한적이 없으면
                if(broken[nr][nc] == -1) {
                    // 다음 목적지가 벽돌이라면
                    if(map[nr][nc] == 1) {
                        pq.push({-(broken_cnt + 1), {nr, nc}});
                    }
                    // 벽돌 없는 빈방이라면
                    else {
                        pq.push({-broken_cnt, {nr, nc}});
                    }
                }
            }
        }
    }

    cout << broken[r-1][c-1];
    return 0;
}