경쟁적 전염 18405

문제

접근 방법

BFS를 활용하는 것은 당연하다. (전파, 증식, 전염 등등... 퍼져나가는 것은 BFS일 가능성이 높다)
바이러스 번호가 낮을수록 먼저 증식하기에 낮은 번호가 우선시되게 하면 된다. 또한 해당하는 목표 지점에 도달한 경우 바로 반환하면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, K, S, X, Y;
    cin >> N >> K;

    vector<vector<int>> map(N, vector<int>(N));
    vector<pair<int, pair<int, int>>> v;
    queue<pair<int, pair<int, int>>> q;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
        {
            int k;
            cin >> k;
            if (k)
            {
                v.push_back({k, {i, j}});
                map[i][j] = k;
            }
        }
    sort(v.begin(), v.end());
    for (auto i : v)
    {
        q.push({0, i.second});
    }
    cin >> S >> X >> Y;
    --X, --Y;
    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();
        if (cur.first == S)
            break;
        for (int j = 0; j < 4; ++j)
        {
            pair<int, int> nextPos = {cur.second.first + dy[j], cur.second.second + dx[j]};
            if (nextPos.first < 0 || nextPos.second < 0 || nextPos.first >= N || nextPos.second >= N || map[nextPos.first][nextPos.second])
                continue;
            if (X == nextPos.first && Y == nextPos.second)
            {
                cout << map[cur.second.first][cur.second.second];
                return 0;
            }
            q.push({cur.first + 1, nextPos});
            map[nextPos.first][nextPos.second] = map[cur.second.first][cur.second.second];
        }
    }
    cout << map[X][Y];
    return 0;
}

풀이

K개의 큐를 두고 시간을 줄여나가며 1부터 K까지 전파하는 방식으로 했었다. 그러자 풀긴 풀었는데 수행 시간이 꽤 많이 나왔다.
다른 사람과 비교해봤더니 어차피 큐는 먼저 들어온 것이 먼저 나가기에 (정렬된 배열도 앞에서부터 확인하면 선입선출이기에) K개의 큐가 아닌 1개의 큐로 관리하는 것이다.

1개의 큐로 관리하게 바꾸었더니 수행 시간이 단축됐다. 효율적으로 작동하게 하려면 좀 더 생각해봐야 하는 것을 다시 한번 깨달았다.