[BOJ] 탈옥 - Compy's Blog

탈옥

TimeLimit	MemoryLimit	Condition	TAG
1s	256MB	2 ≤ h, w ≤ 100	Dijkstra

와.. 문제 드릅게 어렵슨디ㅣㅏ…

아니 심지어 중간에 질문 게시판 열심히 들어가봤는데도 반례가 안 나와서 오답 코드들 몇 개 보고서 좀 비교를 해서 그냥 새롭게 코드를 작성한 후 AC를 맞았습니다..

일단 원래는 그냥 죄수들을 기준으로 중복된 문을 없애고 개수 세기였는데 어떤 case에서 안되는 반례가 있나봅니다. 그래서 다익스트라를 각 죄수들과 출구에서부터 들어오는 걸로 총 3번 실행해서 AC를 맞을 수 있엇는데

아이디어가 진짜 생각해내기 많이 힘들었따…

솔직히 이런 문제는 좋은 문제인 것 같아요 요런 아이디어 아주 재미잇네요… 근데 어렵네요 허허ㅓ허허허허ㅓ허…

풀이 영상

정답 코드

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

using ll = long long;

char stateBoard[105][105];
ll board[105][105][3];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

struct info {
    ll cost;
    int y;
    int x;
};

bool operator>(const info& a, const info& b) {
    return a.cost > b.cost;
}

void bfs(int idx, pair<int, int> start, int h, int w) {
    priority_queue<info, vector<info>, greater<info>> q;
    
    for (int i = 0; i <= h+1; i++) {
        for (int j = 0; j <= w+1; j++) {
            board[i][j][idx] = 1e15;
        }
    }
    
    board[start.first][start.second][idx] = 0;
    q.push({0, start.first, start.second});
    
    while (!q.empty()) {
        info current = q.top(); q.pop();
        ll cost = current.cost;
        int y = current.y;
        int x = current.x;
        
        if (cost > board[y][x][idx]) continue;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (ny < 0 || nx < 0 || ny > h+1 || nx > w+1) continue;
            
            if (stateBoard[ny][nx] == '*') continue;
            
            ll next_cost = cost + (stateBoard[ny][nx] == '#' ? 1 : 0);
            
            if (next_cost < board[ny][nx][idx]) {
                board[ny][nx][idx] = next_cost;
                q.push({next_cost, ny, nx});
            }
        }
    }
}

ll solution(int h, int w, vector<pair<int, int>>& starts) {
    for (auto& pos : starts) stateBoard[pos.first][pos.second] = '.';
    
    bfs(0, {0, 0}, h, w);
    
    bfs(1, starts[0], h, w);
    
    bfs(2, starts[1], h, w);
    
    ll result = 1e15;
    for (int i = 0; i <= h+1; i++) {
        for (int j = 0; j <= w+1; j++) {
            if (stateBoard[i][j] == '*') continue;
            ll total = board[i][j][0] + board[i][j][1] + board[i][j][2];
            total -= 2 * (stateBoard[i][j] == '#');
            result = min(result, total);
        }
    }
    
    return result;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int t;
    cin >> t;
    while (t-- > 0) {
        int h, w;
        cin >> h >> w;
        
        for (int i = 0; i <= h+1; i++) {
            for (int j = 0; j <= w+1; j++) stateBoard[i][j] = '.';
        }
        
        vector<pair<int, int>> starts;
        
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                cin >> stateBoard[i][j];
                if (stateBoard[i][j] == '$') starts.push_back({i, j});
            }
        }
        
        cout << solution(h, w, starts) << "\n";
    }
    return 0;
}