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

문제

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

18405번: 경쟁적 전염

풀이

BFS + 구현으로 해결할 수 있었다.

처음에는 시간 -> 바이러스 종류 -> X좌표 -> Y좌표로 이루어진 4중 for문으로 해결하려다가 시간 초과가 나서 정렬을 통한 풀이로 방법을 바꿨다.
우선순위 큐를 하나 만들어주는데 이 큐가 3개의 자료형 (X좌표, Y좌표, 바이러스의 종류)를 담을 수 있도록 했다. 참고로 자료형 3개 이상을 담을 때는 tuple을 사용하는 것을 추천한다.

이후에 큐를 바이러스 종류에 따라 오름차순 정렬을 해주는 Compare 함수를 만들면 굳이 일일이 바이러스 종류를 확인하지 않아도 순서에 맞게 바이러스가 증식할 수 있도록 만들 수 있다.

큐의 구현이 끝났다면 BFS를 구현해야 하는데 이때 우리는 큐가 빌 때까지 계속해서 탐색하는 BFS가 아닌 바이러스의 종류에 따른 이동 1번과 시간이라는 조건이 있기 때문에 우선 시간에 대해서는 for문으로 감싸주고, 이동 1번이라는 조건은 탐색을 진행하기 전에 큐의 크기를 알아내서 큐의 크기만큼만 탐색을 할 수 있도록 하면 계속해서 탐색하는 것을 막을 수 있다.

이렇게 BFS 구현을 했다면 시간만큼 탐색을 돌리다 마지막에 우리가 원하는 좌표의 바이러스의 종류를 리턴해주면 문제를 해결할 수 있다.

문제를 풀면서 주의할 점은 만약 바이러스가 증식했더라도 바로 큐에 넣지 말아야 하는 것이다. 왜냐하면 증식하자마자 큐에 바로 넣게 돼버리면 해당 좌표는 다음번에 탐색해야 할 좌표인데 이번 턴에 탐색을 돌아버릴 가능성이 존재하기 때문이다.

그래서 필자는 Vector 컨테이너를 하나 만들어서 해당 좌표와 바이러스의 종류를 임시로 담아주고 다음 탐색 차례에 Vector에 있는 값들을 다시 큐에 넣어주어 해결할 수 있었다.

위와 같은 사례를 예시로 들자면 현재 탐색을 진행 중인 큐의 데이터가 (1,1,1), (3,2,2), (3,5,7) 이렇게 3개 있다고 가정하고 이번이 (1,1,1)을 탐색할 차례라고 할 때 증식하자마자 큐에 넣어버리면 바이러스 종류에 따른 오름차순 정렬로 (0,1,1), (3,2,2), (3,5,7)와 같은 잘못된 데이터를 가지고 탐색을 할 수 있는 것이다. 

 

정답 코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <tuple>
#define x first
#define y second

using namespace std;

class cmp {
public: bool operator() (tuple<int, int, int> a, tuple<int, int, int> b) {
		return get<2>(a) > get<2>(b);
	}
};

int n, k, s;
int targetX, targetY;
int board[201][201];
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0, 1, 0 ,-1 };
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, cmp> pq;
vector<tuple<int, int, int>> vec;

void initialValueSet();
int BFS();

int main()
{
	initialValueSet();
	cout << BFS();
}

int BFS()
{
	for (int time = 0; time < s; time++)
	{
		for (int i = 0; i < vec.size(); i++)
		{
			pq.push(vec[i]);
		}
		vec.clear();
		int size = pq.size();
		
		while (size--)
		{
			auto cur = pq.top();
			pq.pop();

			for (int dir = 0; dir < 4; dir++)
			{
				int nx = get<0>(cur) + dx[dir];
				int ny = get<1>(cur) + dy[dir];

				if (nx < 0 || nx >= n || ny < 0 || ny >= n)
				{
					continue;
				}
				if (board[nx][ny] != 0)
				{
					continue;
				}

				board[nx][ny] = get<2>(cur);
				vec.push_back({ nx, ny, board[nx][ny] });
			}
		}
	}

	return board[targetX - 1][targetY - 1];
}

void initialValueSet()
{
	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> board[i][j];
			if (board[i][j] != 0)
			{
				pq.push({ i, j, board[i][j] });
			}
		}
	}

	cin >> s >> targetX >> targetY;
}

시간초과 코드

#include <iostream>
#include <queue>
#define x first
#define y second

using namespace std;

int n, k, s;
int targetX, targetY;
int board[201][201];
bool visited[201][201];
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0, 1, 0 ,-1 };

void initialValueSet();
int BFS();

int main()
{
	initialValueSet();
	cout << BFS();
}

int BFS()
{
	queue<pair<int, int>> q;

	for (int time = 0; time < s; time++)
	{
		for (int num = 1; num <= k; num++)
		{
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					if (visited[i][j] || board[i][j] != num)
					{
						continue;
					}

					q.push({ i, j });
					visited[i][j] = true;

					auto cur = q.front();
					q.pop();

					for (int dir = 0; dir < 4; dir++)
					{
						int nx = cur.x + dx[dir];
						int ny = cur.y + dy[dir];

						if (nx < 0 || nx > n || ny < 0 || ny > n)
						{
							continue;
						}
						if (visited[nx][ny] || board[nx][ny] != 0)
						{
							continue;
						}

						visited[nx][ny] = true;
						board[nx][ny] = n;
					}
				}
			}
		}
	}

	return board[targetX - 1][targetY - 1];
}

void initialValueSet()
{
	cin >> n >> k;

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

	cin >> s >> targetX >> targetY;
}