[백준 18405번 C/C++] 경쟁적 전염

 

[백준 18405번 C/C++] 경쟁적 전염

 

 

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

18405번: 경쟁적 전염

 

---

 

해결전략

 

구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색 (BFS)

 

---

 

코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, k, s, row, column;
vector<vector<int>> v;
int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };

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

	cin >> n >> k;
	v.resize(n + 1, vector<int>(n + 1));

	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pQ;

	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= n; x++) {
			cin >> v[y][x];
			if (v[y][x] != 0) {
				pQ.push({ v[y][x], y, x });
			}
		}
	}

	cin >> s >> row >> column;

	while (s--)
	{
		priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> next_pQ;
		
		while (!pQ.empty())
		{
			int virus, curY, curX;
			tie(virus, curY, curX) = pQ.top();
			pQ.pop();

			for (int i = 0; i < 4; i++) 
			{
				int newY = curY + dirY[i];
				int newX = curX + dirX[i];

				if (newY >= 1 && newY <= n && newX >= 1 && newX <= n && v[newY][newX] == 0) 
				{
					v[newY][newX] = virus;
					next_pQ.push({ virus, newY, newX });
				}
			}
		}
		pQ = next_pQ;
	}

	cout << v[row][column];

	return 0;
}

n = 격자의 크기

k = 바이러스 종 수

s = 총 시간

row와 column = 찾고자 하는 최종 격자 위치.

v = 격자 행렬, 각 셀의 값은 바이러스 번호.

dirY와 dirX = 상하좌우 이동에 대한 행과 열의 이동 정보

1. 크기가 n+1인 2차원 벡터 v 를 생성하고 입력을 저장

2. 바이러스 번호에 따라 우선순위 큐 pQ에 tuple 형태로 바이러스 번호, 현재 위치 (y, x)를 저장

3. 해당 방식은 완료되면 먼저 입력된 바이러스번호에 대해 정렬된 상태로 큐에 저장

 

바이러스 전파 처리:
1. s번의 시간 경과를 반복 처리 while(s--)

2. 각 바이러스에 대한 전파 처리를 위해 우선순위 큐 next_pQ를 생성.

3. 큐에서 전파되지 않은 바이러스 위치를 가져온다. 가져온 위치에서 상하좌우로 이동하는 위치를 계산하고, 그 위치에 미전파 상태인 격자가 있는 경우 바이러스를 전파시키고 해당 위치의 바이러스 정보를 새로운 큐 next_pQ에 저장.

4. 현재 시간의 바이러스 전파 작업을 모두 수행한 후, 새로운 큐인 next_q를 기존 큐 pQ에 연결한다. 다음 시간의 전파를 위해 기존 작업이 끝난 큐의 기록을 새로운 큐의 기록으로 업데이트한다.

최종 결과 출력:
총 시간 s가 경과한 후, (row, column) 위치의 격자 값을 출력한다.

 

 

시간에 따른 바이러스 전파를 효율적으로 처리하기 위해 우선순위 큐를 사용한다. 큐에 저장된 바이러스를 기반으로 전파되지 않은 위치에 전파하고, 새로 전파된 위치를 다음 상황에 사용할 새로운 큐에 저장한다. 이 작업을 반복 수행하여 문제를 해결한다.

 

 

cin >> n >> k;
v.resize(n + 1, vector<int>(n + 1));

격자 크기n과 바이러스 종류 수k를 입력 받고, 격자에 대한 공간을 할당한다.

priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pQ;

바이러스의 종류와 위치 정보를 저장할 priority_queue를 선언한다. priority_queue는 바이러스의 번호가 작은 순서대로(오름차순) 정렬된다.

for (int y = 1; y <= n; y++){
	for (int x = 1; x <= n; x++){
		cin >> v[y][x];
		if (v[y][x] != 0) {
			pQ.push({v[y][x], y, x});
		}
	}
}

격자를 입력받고, 바이러스가 있는 위치를 우선순위 큐에 저장.

cin >> s >> row >> column;

시간s과 최종 위치의 행row와 열column을 입력.

while (s--)
{
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> next_pQ;

바이러스 전파를 처리하기 위한 반복문을 실행하고, 다음 시간의 바이러스 정보를 담을 새로운 우선순위 큐next_pQ를 선언합니다.

	while(!pQ.empty()) {
		int virus, curY, curX;
		tie(virus, curY, curX) = pQ.top();
		pQ.pop();

큐가 빌 때까지 처음 큐에 들어있는 바이러스 정보(바이러스 번호와 현재 위치)를 가져온다.

		for (int i = 0; i < 4; i++) {
			int newY = curY + dirY[i];
			int newX = curX + dirX[i];

			if (newY >= 1 && newY <= n && newX >= 1 && newX <= n && v[newY][newX] == 0) {
				v[newY][newX] = virus;
				next_pQ.push({virus, newY, newX});
			}
		}
	}
	pQ = next_pQ;
}

상하좌우로 이동하는 경우를 확인하여 바이러스 전파를 처리하고, 전파된 바이러스의 정보를 새로운 큐에 저장한다. 작업이 완료되면 새로운 큐를 기존 큐로 업데이트한다.

---