백준 18405번 경쟁적 전염 C++ 풀이

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

18405번: 경쟁적 전염

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

문제 설명이 아주 잘 되어있는 문제로, 이 것을 어떻게,무엇으로 구현할지가 관건인 문제이다.

 

문제의 포인트

클래스의 형식을 활용하여 bfs를 사용할 수 있는가?

배열을 활용하여 for문을 도는데 코드를 정리할 수 있는가? (하면 편리함)

코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int n, k;
int s, x, y;
int arr[200][200]; //전역임으로 0으로 초기화
int dir[4][2]{ {-1,0},{0,-1}, {1,0} ,{0,1} };
class Virus
{
public:
	Virus(int x, int y, int type, int time)
	{
		m_posx = x;
		m_posy = y;
		m_type = type;
		m_time = time;
	}
	bool operator<(Virus& other)
	{
		return m_type < other.m_type;
	}
public:
	int m_posx;
	int m_posy;
	int m_type;
	int m_time;
};
vector<Virus> v;
int main()
{
	//n 시험관 크기 k 바이러스 번호
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] != 0)
			{
				v.push_back(Virus(i, j, arr[i][j], 0));
			}
		}
	}
	sort(v.begin(), v.end());
	//s 시간(초) x 행 y 열
	cin >> s >> x >> y;
	queue<Virus> q;
	for (int i = 0; i < v.size(); i++)
	{
		q.push(v[i]);
	}
	while (!q.empty())
	{
		Virus vir = q.front();
		q.pop();
		if (vir.m_time == s) break;
		for (int i = 0; i < 4; i++)
		{
			int nx = vir.m_posx + dir[i][0];
			int ny = vir.m_posy + dir[i][1];
			//다음 위치로 갈 수 있는지 체크
			if (nx >= 0 && nx < n && ny >= 0 && ny < n)
			{
				if (arr[nx][ny] == 0)
				{
					arr[nx][ny] = vir.m_type;
					q.push(Virus(nx, ny, vir.m_type, vir.m_time + 1));
				}
			}
		}
	}
	cout << arr[x-1][y-1];
}