[BOJ 18128, C++] 치삼이의 징검다리 건너기

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

18128번: 치삼이의 징검다리 건너기

 

 

풀이

물 이동은 1초에 상하좌우 한 번씩 움직이므로 BFS로 만들 수 있습니다.

치삼이는 상하좌우와 대각선을 포함한 8개의 방향으로 움직일 수 있는데, 치삼이가 이동하는데 시간이 걸리지 않는다고 했으므로 치삼이가 도착할 수 있는 시간은 치삼이의 이동 경로중에 제일 늦게 식은 돌의 시간이 됩니다.

그래서 치삼이의 시간을 구하는 것은 다익스트라 알고리즘을 통해 구할 수 있게 됩니다.

 

주의할 점은 시작점과 도착점의 돌이 물에 닿지 않아도 된다는 것 입니다. 그래서 다익스트라를 시작할 때 출발돌이 식은 시간을 무시하고 돌리고, 도착할 때는 도착돌보다 도착점 주변의 돌중에 빨리 식은 돌이 있는지 찾아보면 됩니다.

 

 

 

코드

#include <iostream>
#include <cstring>
#include <queue>
#include <string>
using namespace std;
using ll = long long;
 
const int N = 1001;
int n, w, x, y, S[N][N], visited[N][N], MAP[N][N];
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
int cx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }, cy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
char k;
 
 
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(MAP, -1, sizeof(MAP));
    memset(visited, -1, sizeof(visited));
    memset(S, -1, sizeof(S));
 
    queue<pair<int, int>> q;
    priority_queue<pair<int, pair<int, int>>> pq;
 
    cin >> n >> w;
    for (int i = 0; i < w; i++) {
        cin >> x >> y;
        q.push(make_pair(--x, --y));
        S[x][y] = 0;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> k;
            MAP[i][j] = k - '0';
        }
 
    }
 
    while (!q.empty()) {
        pair<int, int> p = q.front(); q.pop();
        int x = p.first, y = p.second;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < n && S[nx][ny] == -1) {
                S[nx][ny] = S[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
 
    pq.push(make_pair(0, make_pair(0, 0)));
    while (!pq.empty()) {
        pair<int, pair<int, int>> p = pq.top(); pq.pop();
        int t = p.first, x = p.second.first, y = p.second.second;
        if (x == n - 1 && y == n - 1) {
            if (visited[x - 1][y] != -1) t = -min(-t, visited[x - 1][y]);
            if (visited[x][y - 1] != -1) t = -min(-t, visited[x][y - 1]);
            if (visited[x - 1][y - 1] != -1) t = -min(-t, visited[x - 1][y - 1]);
            cout << -t << endl;
            return 0;
        }
        for (int i = 0; i < 8; i++) {
            int nx = x + cx[i], ny = y + cy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < n && MAP[nx][ny] == 1 && visited[nx][ny] == -1) {
                visited[nx][ny] = max(S[nx][ny], -t);
                pq.push(make_pair(-visited[nx][ny], make_pair(nx, ny)));
            }
        }
    }
 
    cout << -1;
}