[3055] 탈출

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

3055번: 탈출

<문제>

2번의 bfs를 진행한다.

첫번째 bfs는 물(*)을 기준으로 모든 정점까지의 최단거리를 dist[][]에 업데이트한다.

두번째 bfs는 고슴도치(S)를 기준으로, 비버의 굴(D)을 목표로 탐색을 진행한다.

 

이때, dist[nextY][nextX] > dist[curY][curX] + 1 을 만족하는 조건을 추가함으로써

물에 빠지지 않는한 이동을 하도록 만들어 준다.

탐색중 한번이라도 비버의 굴에 도달한다면 그때의 turn이 곧 최적해다.

비버의 굴에 도착하지 않은채로 queue가 비었다면, 이동이 불가능하다는 의미로 "KAKTUS"를 출력하면 된다.

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;
int dist[51][51], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
int n, m, endY, endX;
char a[53][53];
vector<pair<int, int>> start;
void init(void) {
    queue<pair<int, int>> q;
    int i;
    fill(&dist[0][0], &dist[50][50], INF);
    for (i = 0; i < start.size(); i++) {
        q.push({start[i].first, start[i].second});
        dist[start[i].first][start[i].second] = 0;
    }
    while (!q.empty()) {
        int S = q.size();
        for (int k = 0; k < S; k++) {
            pair<int, int> cur = q.front();
            q.pop();
            for (i = 0; i < 4; i++) {
                int y = cur.first + dy[i];
                int x = cur.second + dx[i];
                if (y < 0 || x < 0 || y >= n || x >= m) continue;
                if (a[y][x] == '.' &&
                    dist[y][x] > dist[cur.first][cur.second] + 1) {
                    dist[y][x] = dist[cur.first][cur.second] + 1;
                    q.push({y, x});
                }
            }
        }
    }
}
typedef struct {
    int y, x, turn;
} state;
void f(int sy, int sx) {
    bool visited[51][51];
    memset(visited, false, sizeof(visited));
    queue<state> q;
    q.push({sy, sx, 0});
    visited[sy][sx] = true;
    int i;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (cur.y == endY && cur.x == endX) {
            cout << cur.turn;
            return;
        }
        for (i = 0; i < 4; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (a[y][x] == 'X' || visited[y][x] == true) continue;
            if (cur.turn + 1 < dist[y][x]) {
                q.push({y, x, cur.turn + 1});
                visited[y][x] = true;
            }
        }
    }
    cout << "KAKTUS";
    return;
}
int main(void) {
    cin >> n >> m;
    int i, j, startY, startX;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            cin >> a[i][j];
            if (a[i][j] == '*') {
                start.push_back({i, j});
            }
            if (a[i][j] == 'S') {
                startY = i;
                startX = j;
            }
            if (a[i][j] == 'D') {
                endY = i;
                endX = j;
            }
        }
    }
    init();
    f(startY, startX);
    return 0;
}