[C++] BOJ(백준) 18405 경쟁적 전염

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

18405번: 경쟁적 전염

 

BFS 문제다.

전염은 BFS로 풀면 간단할 것 같았는데 우선순위를 어떻게 처리해야 할 지 난감했다.

바이러스 번호, x, y를 하나로 묶어서 정렬을 해야하나 했는데 초마다 정렬해야 할 것 같아서 패스

초만큼 반복을 하고 그 안에서 배열을 계속 반복하며 1일 때만 전염, 그 후 2일 때만 전염으로 하려다가

이것만큼 비효율적인 방법이 없을 것 같아 패스...

 

총 두 가지 방법을 사용해서 문제를 해결했다.

 

문제 설명 부터 하자면 주의점 세 가지 있었다.

1. 한 타임에 한 칸만 이동 가능

=> 초당 반복을 끊어주기 / pair로 묶인 변수에 이동 수도 포함하기

본인은 전자 선택, 후자는 pair가 너무 많아진다고 생각했다.

 

2. 입력받는 x, y좌표가 컴퓨터 상의 좌표(0부터 시작)가 아닌 사람의 좌표(1부터 시작)다.

 

3. 입력으로 s = 0도 들어온다.

=> 경우의 수를 따로 체크해줘야 한다.

처음에는 이 점을 생각하지 못하고 반복문에 들어가지도 못 해 무조건 0이 나왔다.

아래 사진 부분이 이 부분이다. 그러나 해당 테스트 케이스가 없는지 코드에 넣지 않아도 통과 된다...

 

첫번째 방법으로 우선순위 큐를 사용해보는 것은 어떨까 싶었다.

우선순위 큐에 pair 적용법에서 많이 헤매다 결국은 성공했고 이 방법부터 설명하겠다.

 

일반적인 BFS와 같은 형태이나 달라진 점은 크게

1. 큐 -> 우선순위 큐 (오름차순)

2. while문 안에서 큐에 push 하지 않음 (초당 한 칸 이동을 위해)

 

BFS 함수 안에서 원하는 좌표의 바이러스 번호를 반환하면 main이 종료되도록 했다.

함수 실행마다 우선순위 큐를 새로 생성하다 보니 메모리를 많이 차지하는 것 같다.

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

int n, s, x, y, k;
int board[200][200];
// 상하좌우 탐색을 위함
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int BFS() {
	// <바이러스 번호, <행, 열>, 오름차순>
	priority_queue<pair<int, pair<int, int>>, vector< pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			// 바이러스가 존재하면 우선순위 큐에 삽입
			if (board[i][j]) q.push(make_pair(board[i][j], make_pair(i, j)));

	// 큐가 빌 때까지 반복
	while (!q.empty()) {
		int curx = q.top().second.first;
		int cury = q.top().second.second;
		int num = q.top().first;

		q.pop();

		// 상하좌우 4방향 이동을 위함
		for (int i = 0; i < 4; i++) {
			int xx = curx + dx[i];
			int yy = cury + dy[i];

			// 범위를 벗어나면 continue
			if (xx >= n || xx < 0 || yy >= n || yy < 0) continue;

			// 값이 존재하지 않으면 바이러스가 이동
			if (!board[xx][yy]) board[xx][yy] = num;

			// 원하는 좌표에 바이러스가 전염됐다면 바이러스 번호 리턴
			if (xx == x - 1 && yy == y - 1) return board[xx][yy];
		}
	}
	return 0;
}

int main() {
	cin >> n >> k;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) cin >> board[i][j];

	cin >> s >> x >> y;

	// s = 0일 때는 바로 출력 후 종료
	if (!s) {
		cout << board[x - 1][y - 1];
		return 0;
	}

	for (int i = 0; i < s; i++) {
		int re = BFS();
		if (re) {
			cout << re;
			return 0;
		}
	}
	cout << 0;
}

 

속도는 빨랐지만 메모리를 좀 차지하는 경향이 있었다.

 

두 번째 방법은 인터넷의 도움을 조금 받아 벡터와 sort를 사용하는 방법을 선택했다. (방법 힌트만 얻음)

BFS 함수를 따로 만들지 않았으며, 정렬은 처음 한 번만 해주면 됐다.

작은 수에 대해 벡터에 차례대로 삽입하기 때문에

(1, 2) 가 들어 있었다면 (1, 1, 1, 2, 2) 이런식으로 진행이 된다.

 

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

int n, s, x, y, k;
int board[200][200];
// 상하좌우 탐색을 위함
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main() {
	// <바이러스 번호, <행, 열>>
	vector<pair<int, pair<int, int>>> v;

	cin >> n >> k;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
			// 바이러스 번호가 존재한다면 벡터에 push
			if (board[i][j]) v.push_back({ board[i][j], { i, j } });
		}

	cin >> s >> x >> y;
	
	// s = 0일 때는 바로 출력 후 종료
	if (!s) {
		cout << board[x - 1][y - 1];
		return 0;
	}

	sort(v.begin(), v.end());

	for (int t = 0; t < s; t++) {
		// 한 타임에 한 칸만 움직일 수 있으므로 시작 전 벡터의 크기만큼만 반복
		// 벡터에 2개의 원소가 있었다면 2번만 반복, 반복문 안에서 push된 만큼 다음에 반복
		int cnt = v.size();
		for (int j = 0; j < cnt; j++) {
			int curx = v.front().second.first;
			int cury = v.front().second.second;
			int num = v.front().first;

			v.erase(v.begin());

			// 상하좌우 4방향 이동을 위함
			for (int i = 0; i < 4; i++) {
				int xx = curx + dx[i];
				int yy = cury + dy[i];

				// 범위를 벗어나면 continue
				if (xx >= n || xx < 0 || yy >= n || yy < 0) continue;

				// 값이 존재하지 않으면 바이러스가 이동, 벡터에 추가
				if (!board[xx][yy]) {
					board[xx][yy] = num;
					v.push_back({ board[xx][yy], { xx, yy } });
				}

				// 원하는 좌표에 바이러스가 전염됐다면 출력 후 종료
				if (xx == x - 1 && yy == y - 1) {
					cout << board[xx][yy];
					return 0;
				}
			}
		}
	}
	cout << 0;
}

 

앞의 방법과는 정반대로 메모리는 비교적 덜 차지 하지만 시간이 꽤 오래 걸렸다.