백준 18405 경쟁적 전염

문제 URL : https://www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

 

문제접근법 : 난이도가 쉬운 bfs 문제입니다.

 

보드판 사이즈가 200밖에 되질않고

시간은 s가 10000이나 주어집니다.

최악의경우 바이러스 하나만있다고 가정하고 (1,1)에서 심어져서 (200,200) 까지

퍼진다해도 대충계산해도 200+200 즉 400초를 넘을수가없죠 

따라서 bfs를 계속 돌지않도록 더이상 퍼지지않으면 bfs를 탈출하도록 하게 만들었구

굳이 1부터~ k번까지의 바이러스가 퍼져야하기때문에 굳이 전 queue에 담아 사용하지도 않았구

vector를 통해서 담아서 사용했습니다.

board 자체가 visit을 처리할수있기때문에 visit또한 절약할수있구요

 

소스코드 : 

#include <bits/stdc++.h>
using namespace std;
int board[300][300];
int n, k;
int fy, fx, s;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
vector<pair<int, int>> v[1001];
void input()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> board[i][j];
            if (board[i][j])
                v[board[i][j]].push_back({i, j});
        }
    }
    cin >> s >> fy >> fx;
}
bool isrange(int y, int x)
{
    return 0 <= y && y < n && 0 <= x && x < n;
}

void print(int cnt)
{
    cout << cnt << "  : \n";
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
void solve()
{
    int cnt = 0;
    while (cnt < s)
    {
        int flag = 1;
        for (int i = 1; i <= k; i++)
        {
            int size = v[i].size();
            for (int k = 0; k < size; k++)
            {
                for (int j = 0; j < 4; j++)
                {
                    int ny = v[i][k].first + dy[j];
                    int nx = v[i][k].second + dx[j];
                    if (isrange(ny, nx) && board[ny][nx] == 0)
                    {
                        flag = false;
                        board[ny][nx] = i;
                        v[i].push_back({ny, nx});
                    }
                }
            }
        }
        //print(cnt);
        if (flag)
            break;
        cnt++;
    }
    //print(cnt);
    cout << board[fy - 1][fx - 1] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("input.txt", "r", stdin);
    input();
    solve();
}

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.