백준 18405번 경쟁적 전염 문제풀이(C++)

백준 18405번 경쟁적 전염

아이디어

1. 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다
   ==> 그래프 탐색에서 BFS를 사용하자

2. 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다.
   ==> 탐색 순서에 신경을 써야겠네
   ==> vector에 담아서 오름차순으로 정렬한 결과값을 queue에 담아서 탐색해야겠다

3. 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.
   ==> 탐색할 때 조건식은

if (check_out_of_size(size_test_tube, row_of_virus, column_of_virus) || is_exist(test_tube[row_of_virus][column_of_virus]))continue;

이렇게 되겠다

4. 가장 왼쪽 위에 해당하는 곳은 (1,1)
   ==> 결과값 출력할 때 주의해겠다

cout << test_tube[row_to_check - 1][column_to_check - 1] << '\n';

문제풀이

가독성을 신경써서 코드를 짜봤다

#include<bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

typedef pair<int, int> location;
typedef tuple<int, location, int> type_location_time;
typedef vector<vector<int>> square_vector;

#define ROW first
#define COLUMN second
#define TYPE(type_location_time) get<0>(type_location_time)
#define LOCATION(type_location_time) {get<1>(type_location_time).ROW, get<1>(type_location_time).COLUMN}
#define TIME(type_location_time) get<2>(type_location_time)

constexpr int row_to_move[] = { 1,0,-1,0 };
constexpr int column_to_move[] = { 0,1,0,-1 };

bool is_exist(const int virus)
{
	return virus > 0;
}

bool check_out_of_size(const int test_tube_size, const int virus_row, const int virus_column)
{
	if (virus_row < 0 || virus_row >= test_tube_size || virus_column < 0 || virus_column >= test_tube_size) return true;
	return false;
}

void infect_virus(square_vector& test_tube, const int test_tube_size, queue<type_location_time>& viruses, const int time_to_check)
{
	while (!viruses.empty())
	{
		const type_location_time virus{ viruses.front() };
		viruses.pop();

		const int virus_type = TYPE(virus);
		const int time_current = TIME(virus) + 1;

		// end condition
		if (time_current > time_to_check) return;

		for (int move = 0; move < 4; move++)
		{
			const location virus_location = LOCATION(virus);
			const int virus_row = virus_location.ROW + row_to_move[move];
			const int virus_column = virus_location.COLUMN + column_to_move[move];

			if (check_out_of_size(test_tube_size, virus_row, virus_column) || is_exist(test_tube[virus_row][virus_column]))continue;

			test_tube[virus_row][virus_column] = virus_type;
			viruses.push({ virus_type, {virus_row, virus_column}, time_current });
		}
	}
}

void input_variables(queue<type_location_time>& viruses, square_vector& test_tube, const int test_tube_size)
{
	vector<type_location_time> sort_by_virus_type;

	for (int row = 0; row < test_tube_size; row++)
	{
		for (int col = 0; col < test_tube_size; col++)
		{
			int virus_type;
			cin >> virus_type;
			test_tube[row][col] = virus_type;
			if (is_exist(virus_type))
			{
				sort_by_virus_type.push_back({ virus_type,{row, col},0 });
			}
		}
	}

	sort(sort_by_virus_type.begin(), sort_by_virus_type.end());
	for (type_location_time& sort_by_virus_type_element : sort_by_virus_type)
	{
		viruses.push(sort_by_virus_type_element);
	}
}

void solve()
{
	FAST_IO;

	int test_tube_size, max_virus_type;
	cin >> test_tube_size >> max_virus_type;

	queue<type_location_time> viruses;
	square_vector test_tube(test_tube_size, vector<int>(test_tube_size));

	input_variables(viruses, test_tube, test_tube_size);

	int time_to_check, row_to_check, column_to_check;
	cin >> time_to_check >> row_to_check >> column_to_check;

	infect_virus(test_tube, test_tube_size, viruses, time_to_check);

	cout << test_tube[row_to_check - 1][column_to_check - 1] << '\n';
}

int main() {

	solve();

	return 0;
}