백준 18405 c++ "경쟁적 전염" -PlusUltraCode-

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

[필자 사고]

필자는 해당 문제를 BFS로 풀었다. 

이 문제만의 특이 포인트는 다음과 같다.

1. 작은 숫자들의 바이러스들 부터 퍼진다.

2. 모든 숫자들의 바이러스가 퍼지게 되면 1초가 끝난다.

3. 한번 퍼질때 주위 한칸밖에 퍼지지 못한다.

 

필자는 이러한 제약 조건들을 해결하기 위해 우선순위 큐와 일반 큐를 이용하여 문제를 해결했다.

우선순위 큐에는 바이러스 번호들을 기준으로 작은 순서대로 정렬을 하였고 특정 위치들을 우선순위 큐에 넣어서 관리했다.(새로 생성된 바이러스 포함)

 

그리고 매번 큐로 BFS를 실행하여 바이러스 전파를 진행하였다.

개인적으로 BFS와 우선순위 큐를 공부하기 좋은 문제였다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

1. 프로그램 개요

이 프로그램은 N x N 크기의 격자에서 S초 동안 바이러스가 전파되는 과정을 시뮬레이션하는 코드입니다.
바이러스는 BFS(너비 우선 탐색) 방식으로 확산되며, 번호가 작은 바이러스부터 우선적으로 퍼집니다.
최종적으로 S초 후 (X, Y) 위치에 존재하는 바이러스의 번호를 출력합니다.

---

2. 입력 처리 (Input 함수)

Input() 함수는 다음 역할을 수행합니다.

1. 격자의 크기(N)와 바이러스 종류 개수(K) 입력
2. 격자(arr)와 방문 여부(visited) 배열 초기화
3. 격자의 값 입력 및 바이러스 위치 저장
   • 만약 arr[i][k] != 0 (즉, 바이러스가 존재하는 칸)이면 우선순위 큐(pq)에 추가합니다.
   • 이때 번호가 작은 바이러스부터 우선적으로 처리되도록 설정됩니다.
4. 시뮬레이션 시간(S), 목표 좌표(X, Y) 입력

---

3. 바이러스 확산 (BFS 함수)

이 함수는 BFS 탐색을 수행하여 바이러스를 확산시킵니다.

1. myQueue에 저장된 바이러스 위치들을 처리합니다.
2. 현재 위치에서 4방향(상, 하, 좌, 우)으로 이동하면서 다음 조건을 확인합니다.
   • 격자 내부인지 (isInside 함수 활용)
   • 방문하지 않은 위치인지
   • 비어있는 위치(0)인지
3. 위 조건을 만족하면:
   • 해당 위치를 현재 바이러스로 감염시킵니다.
   • 감염된 좌표를 우선순위 큐(pq)에 추가하여 다음 단계에서 확산이 이루어지도록 합니다.

---

4. 시뮬레이션 실행 (Game_Start 함수)

이 함수는 바이러스 확산을 S초 동안 진행합니다.

1. 현재 바이러스가 존재하는 위치를 우선순위 큐에서 꺼내어 myQueue에 저장
2. BFS()를 실행하여 바이러스를 확산
3. resultCount를 증가시키며 1초씩 경과
4. S초가 지나면 (X, Y) 위치의 바이러스 번호를 출력하고 종료

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };


typedef struct Node {
	int sero;
	int garo;
	int weight;
}Node;

struct cmp {
	bool operator()(Node a, Node b) {
		return a.weight > b.weight;
	}
};


vector<vector<int>> arr;
vector<vector<bool>> visited;
priority_queue<Node, vector<Node>, cmp> pq;

bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}

void Input() {
	cin >> N >> K;

	arr.assign(N, vector<int>(N));
	visited.assign(N, vector<bool>(N, false));


	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> arr[i][k];
			if (arr[i][k] != 0) {
				pq.push({ i,k,arr[i][k] });
			}
		}
	}
	cin >> S >> X >> Y;
}

void BFS(queue<Node> & myQueue) {
	
	while (!myQueue.empty()) {
		int nowSero = myQueue.front().sero;
		int nowGaro = myQueue.front().garo;
		int nowWeight = myQueue.front().weight;
		myQueue.pop();
		if (visited[nowSero][nowGaro] == true)continue;
		visited[nowSero][nowGaro] = true;
		
		
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];

			if (isInside(nextSero, nextGaro) == false) continue;
			if (visited[nextSero][nextGaro] == true)continue;
			if (arr[nextSero][nextGaro] != 0)continue;

			arr[nextSero][nextGaro] = nowWeight;
			pq.push({ nextSero,nextGaro,nowWeight });
		}
	}
}

void Game_Start() {

	int resultCount = 0;
	
	while (!pq.empty()) {
		if (resultCount == S) {
			cout << arr[X-1][Y-1];
			return;
		}
		queue<Node> myQueue;

		while (!pq.empty()) {
			int nowSero = pq.top().sero;
			int nowGaro = pq.top().garo;
			int nowWeight = pq.top().weight;
			pq.pop();
			myQueue.push({ nowSero,nowGaro,nowWeight });
		}
		
		BFS(myQueue);
	
		resultCount++;
	}

	cout << arr[X - 1][Y - 1];
}

int main(void) {
	Input();
	Game_Start();
}