[Baekjoon] 18405번: 경쟁적 전염

 

 

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

18405번: 경쟁적 전염

 

---

 

문제 해결 과정

착안

우선순위 큐(priority queue) 자료 구조를 활용하여, 바이러스 번호가 낮은 순으로 먼저 너비 우선 탐색(breadth-first search, BFS)을 수행함으로써 문제를 해결하고자 하였다.

* 우선순위 큐 대신, 배열 및 정렬 알고리즘을 사용하여 해결하면 속도 측면에서 더 유리한 것 같다.

 

구현

좌표를 나타내기 위한 구조체 Coord를 선언하고 연산자 오버로딩(operator overloading)을 통해 '>' 연산자를 정의하여 우선순위 큐를 만들어 문제를 해결하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <queue>

using namespace std;

int TestTube[200][200];
int N, K, S, X, Y;

struct Coord
{
	int Row;
	int Col;

	bool operator>(const Coord& Other) const
	{ return TestTube[Row][Col] > TestTube[Other.Row][Other.Col]; }
};

priority_queue<Coord, vector<Coord>, greater<>> PQ;

void Contaminate(priority_queue<Coord, vector<Coord>, greater<>>& pq, int row, int col, int dRow, int dCol)
{
	int x = row + dRow, y = col + dCol;
	if (x >= 0 && x < N &&
		y >= 0 && y < N &&
		!TestTube[x][y])
	{
		TestTube[x][y] = TestTube[row][col];
		pq.emplace(Coord{ x, y });
	}
}

void Propagate()
{
	if (TestTube[X - 1][Y - 1])
		return;

	priority_queue<Coord, vector<Coord>, greater<>> pq;
	while (!PQ.empty())
	{
		Coord coord = PQ.top();
		PQ.pop();

		if (TestTube[coord.Row][coord.Col])
		{
			Contaminate(pq, coord.Row, coord.Col, 1, 0);
			Contaminate(pq, coord.Row, coord.Col, 0, 1);
			Contaminate(pq, coord.Row, coord.Col, -1, 0);
			Contaminate(pq, coord.Row, coord.Col, 0, -1);
		}
	}

	if (pq.empty())
		return;

	PQ.swap(pq);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> K;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			cin >> TestTube[i][j];
			if (TestTube[i][j])
				PQ.emplace(Coord{ i, j });
		}

	cin >> S >> X >> Y;

	for (int i = 0; i < S; i++)
		Propagate();

	cout << TestTube[X - 1][Y - 1] << "\n";
	return 0;
}

 

실행 결과