18405번 경쟁적 전염

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

bfs 최단거리 tuple 튜플 나동빈 ndb 모의고사 코딩 테스트 코테 복습 필수 추천 boj 백준

그냥 자연수가 나오면 해당 위치를 v에 담고 bfs 실행하면 된다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 202
 
int n, k, m[Max][Max];
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
vector<pair<int, int> > v[Max * 5];
bool visit[Max][Max];
 
void bfs(int s, int ey, int ex)
{
    queue<tuple<int, int, int> > q;
 
    for (int i = 1; i <= k; i++) {
        if (!v[i].empty()) {
            for (auto p : v[i]) {
                q.push({ i, p.first, p.second });
                visit[p.first][p.second] = true;
            }
        }
    }
 
    while (!q.empty() && s--)
    {
        int qs = q.size();
 
        while (qs--)
        {
            int num, r, c;
            tie(num, r, c) = q.front();
 
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= n || x < 0 || x >= n || visit[y][x]) {
                    continue;
                }
 
                m[y][x] = num;
                visit[y][x] = true;
                q.push({ num, y, x });
            }
        }
    }
 
    printf("%d\n", m[ey][ex]);
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%d %d", &n, &k);
 
    int idx = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &m[i][j]);
 
            if (m[i][j]) {
                v[m[i][j]].push_back({ i, j });
            }
        }
    }
 
    int s, y, x;
 
    scanf("%d %d %d", &s, &y, &x);
 
    bfs(s, y - 1, x - 1);
 
    return 0;
}