[18405] 경쟁적 전염

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

18405번: 경쟁적 전염

<문제>

bfs를 여러번 돌려주는 시뮬레이션을 진행할 수도 있지만,

거꾸로 생각하여 (X, Y)에서 최단거리->최소번호순서로 탐색을 진행해줄 수 있다.

현재 거리가 S이상일때에는 가지치기로 잘라주고, 도중에 바이러스를 만났어도 바로 리턴하지 않고

거리가 동일하면서 번호가 더 낮은 바이러스가 있는지를 탐색해준다.

거리 S이상인 바이러스를 만나지 못했다면, 반대로 바이러스가 시작점으로 오기 위해

S턴보다 더 많은 시간을 요하니 0을 리턴해줄 수 있다. 

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, k, S, X, Y, a[201][201], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
bool visited[201][201];
typedef struct {
    int y, x, turn;
} state;
int f(int sy, int sx) {
    queue<state> q;
    q.push({sy, sx, 0});
    visited[sy][sx] = true;
    int ans = 1e9;
    int minTurn = 0;
    bool flag = false;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (cur.turn >= S) continue;
        if (flag && cur.turn > minTurn) continue;
        for (int 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 >= n) continue;
            if (flag && a[y][x] > 0) ans = min(a[y][x], ans);
            if (a[y][x] > 0 && flag == false) {
                flag = true;
                ans = a[y][x];
                minTurn = cur.turn;
            }
            if (a[y][x] == 0 && visited[y][x] == false) {
                q.push({y, x, cur.turn + 1});
                visited[y][x] = true;
            }
        }
    }
    if (ans == 1e9) ans = 0;
    return ans;
}
int main(void) {
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> a[i][j];
    cin >> S >> X >> Y;
    cout << f(X - 1, Y - 1);
    return 0;
}