[백준][C++] 18405 경쟁적 전염

18405. 경쟁적 전염
문제 풀이

18405번: 경쟁적 전염

 

나 BFS로 풀어주세요!! 라고 외치고 있는 문제... 친히 BFS로 풀어주었다.

알고리즘 설계

1. (0,0)부터 (n,n)까지 차례대로 바이러스인지 검사를 한다.
2. 좌표(x, y), 바이러스 번호, 감염된 날을 queue에 넣어준다.
3. 새로 감염된 아이를 queue에 넣어줄 때 중앙에 있는 기존 바이러스(queue.top())의 감염된 날 + 1을 넣어주었다.
4. queue의 top의 날이 S day가 넘어간다면 전염을 중지했다. 즉, while문을 나갔다.
5. field[x-1][y-1]에 있는 상태를 출력한다.

다만... 문제를 잘 안 읽은 나는... 코드를 다 쓰고 제출을 하고서야

이 조건을 읽게 되었다.

그래서 while과 pair과 queue를 사용한 기존 코드에서, struct와 priority_queue를 사용했다.

우선 순위 큐를 사용할 때는 감염된 날짜를 먼저, 그 다음에 감염 번호대로 정렬해주었다.

코드

#include<bits/stdc++.h>
using namespace std;

int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { 1, 0, -1, 0 };

int field[200][200];

struct virus
{
    int y, x, virus, day;

    // 날짜순, 바이러스 번호 순으로 정렬
    bool operator>(const struct virus& v) const
    {
        if (day == v.day)
            return virus > v.virus;

        return day > v.day;
    }
};

priority_queue<virus, vector<virus>, greater<virus>> q;

int main()
{
    int n, k, x, y, s;
    cin >> n >> k;

    for (int y = 0; y < n; y++)
    {
        for (int x = 0; x < n; x++)
        {
            int v;
            cin >> v;
            field[y][x] = v;

            if (v > 0)
            {
                q.push({ y,x,v,1 });
            }
        }
    }

    cin >> s >> x >> y;

    // BFS
    while (!q.empty())
    {
        // s day가 지나면 전염을 멈춘다
        if (q.top().day > s) break;

        virus front = q.top();
        q.pop();

        // 사방으로 인접한 요소들을 전염시킨다
        for (int i = 0; i < 4; i++)
        {
            int nx = front.x + dx[i];
            int ny = front.y + dy[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= n || field[ny][nx] > 0) continue;

            field[ny][nx] = front.virus;

            q.push({ ny, nx, front.virus, front.day + 1 });
        }
    }

    cout << field[x - 1][y - 1];
}

재미있었던 문제 ^~^

이제 구조체를 쓰고 연산자 오버로딩에 익숙해진 것 같아서 기분이 좋다!!