[G5] 백준 18405번 경쟁적 전염 C++ 플러드 필, 우선순위 큐

리뷰

 

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

우선순위 큐를 사용해 번호가 낮은 바이러스부터 플러드필을 통해 퍼뜨리고, S초 뒤 특정 좌표의 값을 출력하는 문제

 

 

전역 변수

• n : 맵의 한 변의 길이를 저장하기 위한 변수
• k : 주어지는 바이러스의 종류 개수를 저장하기 위한 변수
• lst : 맵 정보를 저장하기 위한 정수형 배열
• v : 방문 처리를 체크하기 위한 논리형 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 시뮬레이션에 사용하기 위한 x, y좌표와 바이러스 번호를 정의하기 위한 구조체, 바이러스 번호를 기준으로 오름차순 정렬한다.
• virus : 플러드 필에 사용하기 위한 Pos타입의 우선순위 큐

 

함수

1. solution

int solution()

 

s초간 바이러스를 퍼뜨리고 맵 상에서 x, y좌표의 값을 출력하는 함수

1. 변수 s, x, y에 값을 입력 받는다.
2. s번의 while루프를 순회하며 floodfill함수를 호출해준다.
3. lst에 x, y좌표에 해당하는 값을 리턴해 준다.

 

2. floodfill

void floodfill()

 

플러드 필을 통해 바이러스의 전염을 시뮬레이션 하기 위한 함수

1. Pos타입의 우선순위 큐 next를 초기화 해준다.
2. virus가 빌 때 까지 while루프를 수행한다.
3. 각 루프마다 virus에서 요소를 하나씩 빼내어 Pos타입의 변수 pos에 저장해 준다.
4. pos의 각 값을 정수형 변수 cx, cy, cN으로 파싱해 준다.
5. 4방향 탐색을 진행하며 맵의 범위 안에 있으며 방문처리 되어 있지 않으면 이동을 시작한다.
6. 이동 후에는 방문처리 후 맵 상에서 해당 값을 cN으로 변경해 준다.
7. next에 이동한 좌표와 바이러스 번호를 push해준다.
8. 루프가 종료된 후 swap메서드를 통해 next와 virus를 서로 바꾸어 준다.

 

문제풀이

1. n, k값을 입력받아준다.
2. n * n크기의 맵에 초기값을 입력 받아준다.
3. 초기값이 0이 아닌 경우 virus에 해당 좌표와 번호를 push해주고, 방문처리를 진행해 준다.
4. solution함수를 호출하고 받은 리턴값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• solution함수에서 x, y좌표를 리턴할 땐 각 좌표를 전위감소 시킨 후에 리턴해 주었다.
• 입력되는 좌표 값이 1-based-index로 주어지므로 이는 맵 입력을 1부터 받아도 된다, 선택 사항

 

정답 코드

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

int n, k;
int lst[200][200];
bool v[200][200];
int dx[] = { 1, -1, 0 ,0 };
int dy[] = { 0, 0, 1, -1 };

struct Pos {
	int x, y, N;
	bool operator<(const Pos& other) const {
		return N > other.N;
	}
};
priority_queue<Pos> virus;

void floodfill() {
	priority_queue<Pos> next;
	while (!virus.empty()) {
		Pos pos = virus.top(); virus.pop();
		int cx = pos.x, cy = pos.y, cN = pos.N;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n && !v[nx][ny]) {
				v[nx][ny] = 1;
				lst[nx][ny] = cN;
				next.push({ nx, ny, cN });
			}
		}
	}
	swap(next, virus);
}

int solution() {
	int s, x, y; cin >> s >> x >> y;
	while (s--) floodfill();
	return lst[--x][--y];
}

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

	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> lst[i][j];
			if (lst[i][j]) {
				virus.push({ i, j, lst[i][j] });
				v[i][j] = 1;
			}
		}
	}
	cout << solution();
}