[BOJ/18405] 경쟁적 전염, c++

🔗 링크

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

18405번: 경쟁적 전염

https://github.com/jokj624/PS/blob/master/15000-20000/18405.cpp

jokj624/PS

 

🤯 한줄 후기

 한번에 효율적인 코드를 짜고 싶다. 🤔

🤷 문제

👩‍💻 풀이

단순한 BFS 문제이다. 근데 고려해야할 점이 조금 있는데 문제에 나와있듯, 종류 번호가 낮은 바이러스부터 증식한다는 점이다. 

처음에 이 이유로 우선순위 큐를 썼는데 우선순위 큐는 삽입 때마다 heap 정렬이 일어나 이 문제 구현에는 적합하지 않은 것을 확인했다. 그래서 그냥 큐로 바꿨다가 어쨌든 매 초마다 sorting이 일어나야 하니 vector로 구현하기로 했다.

 

virus 구조체를 만들어 virus 종류 번호와 위치 좌표를 벡터에 저장해준다. 매 초마다 virus가 저장된 벡터를 sorting해준다. 바이러스 종류 번호가 낮은 것 부터 앞에 오도록!

그리고 BFS 를 통해 벡터에 현재 있는 virus들을 순서대로 상-하-좌-우로 퍼지게 한다. 

 

visit vector는 필요없다. 어차피 바이러스가 없는 칸은 0이고, 있는 칸은 종류 번호가 채워져있기 때문에 그것으로 충분히 방문 여부를 알 수 있다.

 

제출했을 때, TLE가 발생했는데 곰곰히 생각해보다가 S초가 되기 전에 이미 X,Y 칸에 바이러스가 채워졌다면 더이상 볼 필요 없는걸 체크하지 못했어서 break문을 추가 해줬더니 바로 통과했다.

💻 코드

//AC
//BOJ 18405 경쟁적 전염
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int arr[202][202];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};  //상하좌우 좌표 배열
struct Virus{
	int virus;
	int x;
	int y;
};   //Virus 구조체, 종류, 위치 정보 담는다.
bool cmp(const Virus& v1, const Virus& v2){
	return v1.virus < v2.virus;
}   // virus 종류가 낮은 것 부터 정렬
int main(){
	vector<Virus> vec;
	int N, K, S, X, Y;
	scanf("%d %d", &N, &K);
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			scanf("%d", &arr[i][j]);
			if(arr[i][j] >= 1 && arr[i][j] <= K){
				vec.push_back({arr[i][j], i, j});   // 바이러스 정보 push 
			}
		}
	}
	scanf("%d %d %d", &S, &X, &Y);
	int s = 0;
	while(s < S){  // 초가 아직 S에 도달하지 못했다면
		sort(vec.begin(), vec.end(), cmp);  //1초 증가할 때마다 새로 sort 
		int len = vec.size();
		for(int j=0; j<len; j++){
			Virus v = vec[j];
			for(int i=0; i<4; i++){
				int nx = v.x + dx[i];
				int ny = v.y + dy[i];   
				if(nx <= 0 || ny <= 0 || nx > N || ny > N)	continue;  //경계선 예외 처리
				if(!arr[nx][ny]){
					arr[nx][ny] = v.virus;  // 바이러스 채우기
					vec.push_back({arr[nx][ny], nx, ny});
				}
			}
		}
		if(arr[X][Y] > 0)	break;  // s < S 일 때, 이미 채워졌다면 더 이상 볼 필요 없다. 
		s++;  //1초 증가시킨다
	}
	printf("%d", arr[X][Y]);
	return 0;
}

사실 풀고 나서 다른 분들은 어떻게 풀었지? 하고 구경해봤는데

매 초마다 sort를 한 건 엄청 비효율적인 코드였다! 

맨 처음에만 sort를 해주면 그 이후로는 알아서 종류가 낮은 바이러스 부터 벡터에 담길 것이다. 그러니까 결국 처음에만 정렬해주고 시작하면 뒤에는 알아서 낮은 번호부터 들어온다는 것이다.

코드 한줄만 수정해주고 다시 제출했더니 무려 4ms나 줄어들었다.

//AC
//BOJ 18405 경쟁적 전염
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int arr[202][202];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
struct Virus{
	int virus;
	int x;
	int y;
};
bool cmp(const Virus& v1, const Virus& v2){
	return v1.virus < v2.virus;
}
int main(){
	vector<Virus> vec;
	int N, K, S, X, Y;
	scanf("%d %d", &N, &K);
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			scanf("%d", &arr[i][j]);
			if(arr[i][j] >= 1 && arr[i][j] <= K){
				vec.push_back({arr[i][j], i, j});
			}
		}
	}
	scanf("%d %d %d", &S, &X, &Y);
	int s = 0;
    sort(vec.begin(), vec.end(), cmp);
	while(s < S){
		int len = vec.size();
		for(int j=0; j<len; j++){
			Virus v = vec[j];
			for(int i=0; i<4; i++){
				int nx = v.x + dx[i];
				int ny = v.y + dy[i];
				if(nx <= 0 || ny <= 0 || nx > N || ny > N)	continue;
				if(!arr[nx][ny]){
					arr[nx][ny] = v.virus;
					vec.push_back({arr[nx][ny], nx, ny});
				}
			}
		}
		if(arr[X][Y] > 0)	break;
		s++;
	}
	printf("%d", arr[X][Y]);
	return 0;
}

 

아직도 한번에 효율적이게 코드를 짜려면 멀었다.