[C++/18405] 경쟁적 전염 - using BFS

문제

 

 

아이디어: BFS

바이러스의 위치 좌표를 queue에 넣어서 이를 확인하며 바이러스가 진행할 수 있는 칸의 값을 바꾸며 탐색을 진행한다.

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

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

int main()
{
    // N(시험관 크기), K(바이러스 종류)
    int N, K;
    
    cin>>N>>K;
    vector<vector<int>> v(200, vector<int>(200, 0));
    vector<pair<int, int>> virus[1001];
    
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < N;j++)
        {
            int temp;
            cin>>temp;
            
            v[i][j] = temp;
            if (temp != 0)
                virus[temp].push_back({i ,j});
            
        }
    }
    
    // S초 후에 (X, Y) 좌표에 있는 바이러스 종류
    int S, X, Y;
    
    cin>>S>>X>>Y;
    
   // 바이러스 좌표(행, 열), 바이러스의 종류, 지난 시간을 저장
    queue<pair<pair<int, int>, pair<int, int>>> q;
    
    for(int i = 1;i <= K;i++)
    {
        for(int j = 0;j < virus[i].size();j++)
        {
            q.push({{virus[i][j].first, virus[i][j].second}, {i, 0}});
        }
    }

	// BFS 탐색 진행
    while (!q.empty())
    {
        auto item = q.front();
        q.pop();
        
        int r = item.first.first;
        int c = item.first.second;
        int vs = item.second.first;
        int time = item.second.second;
        
        // 특정 시간이 되면 바로 종료
        if (time == S)
            break;
        
        // 바이러스가 진행 가능한 동 서 남 북 4개의 방향 다 확인
        for(int dir = 0;dir < 4;dir++)
        {
            int tempR = r + dx[dir];
            int tempC = c + dy[dir];
            
            // 바운더리 체크
            if (tempR < 0 || tempC < 0 || tempR >= N || tempC >= N)
                continue;
            
            // 만약에 0인 경우 바이러스가 진행하도록 값을 바꾸고 queue에 좌표를 넣음
            // 이때 시간은 (현재 시간 + 1)
            if (v[tempR][tempC] == 0)
            {
                v[tempR][tempC] = vs;
                q.push({{tempR, tempC}, {vs, time + 1}});
            }
        }
        
    }
    
    cout<<v[X - 1][Y - 1]<<endl;
    
    return 0;
}