백준/18405번/경쟁적 전염/골드5

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

문제 설명

Site: Baekjoon
Number: 18405
Category: BFS
Rank: Gold 5

N x N 크기의 2차원 배열에서 바이러스의 번호와 위치가 입력으로 주어진다.

바이러스들은 한 번에 상하좌우에 전염될 수 있고, 적은 숫자를 가진 바이러스 부터 전염된다.

이미 감염된 칸은 다시 감염될 수 없다.

첫 입력때만 바이러스의 번호가 적은 순으로 정렬하면 이 후 BFS를 진행하며 자동적으로 적은 바이러스의 번호 순으로 감염이 진행됨으로 처음에만 정렬을 한번 진행한다.

정렬된 deque를 입력된 S번 만큼 감염을 진행하여 문제를 해결하였다. 이 때 정렬 후 queue에 집어넣어 해결하여도 된다.

#include <iostream>
#include <algorithm>
#include <deque>

#define TIII tuple<int, int, int>

//좌상우하 순 방향 배열
int dirx[4] = { 0, -1, 0, 1 };
int diry[4] = { -1, 0, 1, 0 };

using namespace std;

int arr[201][201];

void Infect(int x, int y, deque<TIII>& dq, int& N)
{
	int num = arr[x][y];

	for(int i = 0; i < 4; i++)
	{
		int newx = x + dirx[i];
		int newy = y + diry[i];

		//N x N을 벗어났거나 감염이 되어있는지 확인
		if (newx < 1 || newx > N || newy < 1 || newy > N || arr[newx][newy] != 0)
			continue;

		arr[newx][newy] = num;

		//새롭게 감염된 칸은 다시 deque에 넣어준다
		dq.emplace_back(make_tuple(newx, newy, arr[newx][newy]));
	}
}

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

	deque<TIII> dq;

	int N, K, S, X, Y;
	cin >> N >> K;

	for(int i = 1; i < N+1; i++)
	{
		for(int j = 1; j < N+1; j++)
		{
			cin >> arr[i][j];

			if (arr[i][j] != 0)
				dq.emplace_back(make_tuple(i, j, arr[i][j]));
		}
	}

	//번호가 작은순으로 정렬
	sort(dq.begin(), dq.end(), [](TIII a, TIII b)
	{
		return get<2>(a) < get<2>(b);
	});

	cin >> S >> X >> Y;

	for(int i = 0; i < S; i++)
	{
		//현재 deque에 들어있는 수 만큼만 감염을 진행
		int num = dq.size();

		for(int j = 0; j < num; j++)
		{
			Infect(get<0>(dq[0]), get<1>(dq[0]), dq, N);
			dq.pop_front();
		}
	}

	cout << arr[X][Y];

	return 0;
}