백준 20926번 얼음 미로

문제 요약

가로 세로가 최대 500인 맵이 주어진다. 시작점과 도착점이 주어졌을 때, 도착점에 도착이 가능하다면 최단 시간을, 안되면 -1을 출력하면 된다.

풀이

삼성 A형 같은 느낌의 문제다. 문제에서 주어진 조건을 잘 읽고 그대로 구현을 잘해준 다음에 다익스트라를 돌리면 된다.

미끄러졌을 때, 벽으로 가거나 구멍으로 빠지면 그건 움직일 수 없는 경우이다. 조심하자.

돌에 부딪히거나 도착점에 도착해야만 멈추는 게 가능하다.

모든 점 $(i,j)$에 대해서 위, 오른쪽, 아래, 왼쪽으로 쭉 가면서 돌을 만나면 그 지점과 $(i,j)$를 이동에 드는 시간만큼의 간선으로 이어주면 된다.

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 505;
const int MAXM = 505;
const int INF = 1e9;
int N, M;
int board[MAXN][MAXM];
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};
int sy, sx, ty, tx;
vector<vector<pair<int,int>>> G(MAXN*MAXM);

int conv(int y, int x) {
    return y*M + x;
}

bool valid(int y, int x) {
    return 0<=y && y<N && 0<=x && x<M && board[y][x] != INF;
}

void dijkstra(vector<int> &dist, int src) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    dist[src] = 0;
    pq.emplace(dist[src], src);
    while(!pq.empty()) {
        int cur = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if(dist[cur] < d) continue;
        for(pair<int,int> p : G[cur]) {
            int v = p.first;
            int w = p.second;
            if(dist[v] > d + w) {
                dist[v] = d + w;
                pq.emplace(dist[v], v);
            }
        }
    }
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> M >> N;
    for(int i=0;i<N;++i) {
        string s; cin >> s;
        for(int j=0;j<M;++j) {
            if(s[j] == 'E') {
                ty = i; tx = j;
                board[i][j] = 0;
            }
            else if(s[j] == 'R') {
                board[i][j] = -1;
            }
            else if(s[j] == 'T') {
                sy = i; sx = j;
                board[i][j] = 0;
            }
            else if(s[j] == 'H') {
                board[i][j] = INF;
            }
            else board[i][j] = s[j] - '0';
        }
    }
    for(int i=0;i<N;++i) {
        for(int j=0;j<M;++j) {
            if(i == ty && j == tx) continue;
            if(board[i][j] == INF || board[i][j] == -1) continue;
            for(int k=0;k<4;++k) {
                int y = i, x = j, d = 0;
                while(valid(y, x)) {
                    y += dy[k]; x += dx[k];
                    if(y == ty && x == tx) break;
                    if(board[y][x] == -1) {
                        y -= dy[k]; x -= dx[k];
                        break;
                    }
                    d += board[y][x];
                }
                if(valid(y, x) && (y != i || x != j)) {
                    int u = conv(i, j);
                    int v = conv(y, x);
                    G[u].emplace_back(v, d);
                }
            }
        }
    }
    vector<int> dist(MAXN*MAXM, INF);
    dijkstra(dist, conv(sy, sx));
    if(dist[conv(ty, tx)] == INF) cout << -1 << '\n';
    else cout << dist[conv(ty, tx)] << '\n';
    return 0;
}