[BOJ/C++] 18405 - 경쟁적 전염
https://www.acmicpc.net/problem/18405
문제는 간단합니다.
n*n 시험관에 바이러스 번호에 번호가 매겨져있고, 번호 순서대로 주변 한칸씩 퍼뜨리는 연산을 s번 돌리는 문제입니다.
예를 들어 바이러스가 1,2,3번이 있고, s=3이라면
1,2,3, 1,2,3, 1,2,3 순서대로 바이러스를 퍼뜨립니다.
되게 간단한 문제라 이번 포스팅에서는 문제를 푸는 방법보다는 코드를 최적화 하는 방법에 초점을 맞춰서 작성하고자 합니다. 총 9단계를 거쳐서 코드를 개선해나가보겠습니다!
우선 첫번째 코드입니다.
#include<bits/stdc++.h>
using namespace std;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int board[202][202];
int vis[202][202];
int n,k;
void spread(){
memset(vis,0,sizeof(vis));
for(int idx=1;idx<=k+1;idx++){
for(int i=0;i<n;i++) for(int j=0;j<n;j++){
if(vis[i][j]) continue;
if(board[i][j]!=idx) continue;
for(int dir=0;dir<4;dir++){
int nx = i + dx[dir];
int ny = j + dy[dir];
if(nx<0||nx>=n||ny<0||ny>=n) continue;
if(vis[nx][ny]) continue;
if(board[nx][ny]!=0) continue;
board[nx][ny] = idx;
vis[nx][ny] = 1;
}
}
}
}
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>>board[i][j];
int s,x,y; cin>>s>>x>>y;
for(int i=0;i<s;i++){
spread();
}
cout<<board[x-1][y-1]<<'\n';
}
문제에서 하라는대로 그대로 구현해보았습니다.시험관의 상태를 board에 저장하고, spread함수를 s번 호출한 후 답을 구합니다.spread에서 가장 바깥쪽 반복문은 바이러스의 번호(idx), 그리고 각 번호에 해당하는 바이러스를 board에서 찾고, 한칸씩 BFS를 진행합니다.
당연하겠지만 이대로 제출하면 시간초과가 발생합니다.그도 그럴 것이,보드판의 크기 n은 최대 200.바이러스의 종류 k는 최대 1,000.반복횟수 s는 최대 10,000으로 위의 경우엔 spread 함수의 시간복잡도는 O(k * n * n) = O(40,000,000)이고,따라서 전체 시간복잡도는 (spread의 시간복잡도) * s = O(400,000,000,000)입니다. 1초에 1억번 연산이 가능하다고 하면, 1시간 좀 넘는 시간이 걸리겠네요.
자 그럼 시간을 조금 더 줄여봅시다.일단 spread 함수의 호출 횟수를 줄이는 방법이 있을까요?
방법이 있긴 합니다. spread 함수를 호출해도 더이상 board의 상태가 변화하지 않는다면, 더이상 spread를 호출 할 필요가 없어지겠죠?하지만 아쉽게도 이걸로는 유의미한 최적화를 이뤄낼 수 없을 것 같습니다...
그럼 spread 함수 내부를 최적화 하는 것이 더 효과적일 것 같네요.
spread 함수가 하는 일을 쪼개봅시다.1. 현재 탐색할 바이러스 번호 지정하기 : 이때 바이러스 번호를 idx라고 합시다.2. 보드를 전부 탐색하면서 idx 바이러스의 위치를 찾고, 주변 4칸에 퍼뜨리기.
위의 spraed 함수의 2번 과정에서 매번 i번 바이러스가 board의 어느 위치에 있는지 찾습니다.그럼 i번 바이러스가 어디에 위치하고있는지 미리 찾아서 저장해놓고, 필요할때마다 바로바로 위치를 가져올 수 있다면?매번 n*n의 시간을 써서 위치를 찾을 필요가 없게 되겠네요! (그리고 포스팅하면서 알았는데, 굳이 vis배열에 방문 여부를 저장할 필요도 없겠네요. 이것도 지워줍시다..)
그럼 코드를 한번 수정해봅시다.
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define X first
#define Y second
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int board[202][202];
map<int,set<pii>> idx;
int n,k;
void spread(){
for(int i=1;i<=k;i++){
set<pii> tmp = idx[i];
for(auto cur : tmp){
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(board[nx][ny]!=0) continue;
board[nx][ny] = i;
idx[i].insert({nx,ny});
}
}
}
}
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>>board[i][j];
idx[board[i][j]].insert({i,j});
}
int s,x,y; cin>>s>>x>>y;
for(int i=0;i<s;i++){
spread();
}
cout<<board[x-1][y-1]<<'\n';
}(코드 가독성을 위해 따로 매크로를 지정해주었습니다.)
idx라는 이름의 map을 하나 선언해주었습니다.
key값으로는 바이러스의 번호, value값은 key번 바이러스의 위치를 담은 set을 지닙니다.
board를 입력받으면서 idx도 같이 갱신해주었고,
spread 함수에서 매번 바이러스를 찾아다니지 않고, i번 바이러스의 위치를 담은 idx[i]를 순회하며 배열을 업데이트합니다.
음 좋습니다. 그럼 한번 제출해볼까요?
시간초과가 발생했습니다...
생각해보면, 앞선 코드와 크게 다를 바가 없습니다. 극단적인 경우엔 idx[i]의 크기 합은 최악의 경우 n*n이 될것이고, 아까처럼 board의 전체를 순회하는 것과 마찬가지이기 때문입니다.(board의 모든칸이 1로만 채워져있다면, idx[1]의 크기는 n*n이 되겠죠..)
또, idx[i]에는 굳이 탐색할 필요가 없는 좌표도 가지고 있습니다.예제 1번의 (0,0)을 봅시다.초기 idx[1]에는 (0,0)이 저장되어있을 것이고,spread함수를 한번 호출하면 idx[1]에는 (0,0), (1,0), (0,1)이 저장될 것입니다.그럼 이후 spread호출 시에 (0,0)이 호출될 필요가 있을까요? 이미 (0,0)이 호출되어 주변칸에 대한 연산을 진행했으므로, 이걸 계속 보관하고있다면 계속해서 불필요한 연산이 진행될 것입니다.
따라서 이미 호출해서 연산을 진행했던 칸은 idx[i]에서 제거해줍시다.
void spread(){
for(int i=1;i<=k;i++){
set<pii> tmp;
for(auto cur : idx[i]){
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(board[nx][ny]!=0) continue;
board[nx][ny] = i;
tmp.insert({nx,ny});
}
}
idx[i] = tmp;
}
}
이 전 코드에서 spread 함수만 변경했습니다.
tmp를 선언하여 새로 추가된 좌표를 저장해주고, idx[i]에 덮어씌웁니다.
이로써 idx[i]에는 바이러스가 위치한 구역의 가장자리만 저장될 것 입니다.
좋습니다! 한번 제출해볼까요?
드디어 AC를 받았습니다!
하지만 이대로 끝낼거면 포스팅을 쓰지도 않았을 겁니다.
코드 실행시간이.. 조금 높습니다. 저의 경우에는 실행 시간이 776ms가 나왔습니다. 흠... 조금만 최적화를 해볼까요?
일단 우리의 코드에서 idx의 자료형은 map입니다!
map의 경우 조회, 삽입, 삭제가 O(logN)의 시간이 걸립니다.
map말고 조회, 삽입, 삭제가 O(1)인 unordered_map으로 바꿔주면 조금 더 빨라질 것 같네요.
unordered_map<int,set<pii>> idx;
unordered_map으로 바꾸고 제출하니 시간이 208ms가 나왔습니다!
이전 코드에 비해서 3배 이상 실행시간이 감소했습니다!
엇 그러면 set도 unordered_set으로 바꾸면 더 빠르지 않을까? 하는 생각이 듭니다.
set도 map과 마찬가지로 조회, 삽입, 삭제가 O(logN)이지만, unordered_set은 O(1)이거든요!
그래서 바꾸고 제출하려니... 컴파일 에러가 날 것입니다.
unordered_set, unordered_map은 key값으로 pair를 받지 못하기 때문입니다.
pair형에 대한 해시함수를 따로 정의해주면 되긴 하지만... 투머치이기도 하고.. 조금 귀찮을 것 같습니다.
여기서 꼼수를 조금 부려볼까요?
배열이 2차원이 아니라 1차원이라고 생각해봅니다.그럼 모든 좌표 (i,j)가 i*n + j로 일대일 대응할 수 있게 됩니다.n은 최대 200이므로 i*n+j는 커봐야 399,999입니다.이로써 pair<int,int>형 자료를 int형으로 변환해 줄 수 있고, 그럼 set에 pair가 아닌 int를 넣을 수 있겠네요!
좌표를 int형 정수로 치환하고, set을 unordered_set으로 바꿔줍시다.
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define X first
#define Y second
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int board[202][202];
unordered_map<int,unordered_set<int>> idx;
int n,k;
void spread(){
for(int i=1;i<=k;i++){
unordered_set<int> tmp;
for(auto cur : idx[i]){
for(int dir=0;dir<4;dir++){
int nx = cur/n + dx[dir];
int ny = cur%n + dy[dir];
if(nx<0||nx>=n||ny<0||ny>=n) continue;
if(board[nx][ny]!=0) continue;
board[nx][ny] = i;
tmp.insert(nx*n+ny);
}
}
idx[i] = tmp;
}
}
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>>board[i][j];
idx[board[i][j]].insert(i*n+j);
}
int s,x,y; cin>>s>>x>>y;
for(int i=0;i<s;i++){
spread();
}
cout<<board[x-1][y-1]<<'\n';
}
(x,y)를 정수로 치환하려면 x*n+y에 대입하고,
반대로 정수 N을 (x,y)로 치환하려면 (N/n, N%n)에 대입하면 됩니다.
이 상태로 한번 돌려봅시다!
음.. 돌긴도는데 344ms가 나왔네요.
엇? 아까 set을 쓸때보다 느려졌습니다! 어떻게 된 걸까요?
제 생각에는
unordered_set, unordered_map가 속도가 빠른 이유는 해시함수를 이용하기 때문입니다.
이러한 자료형은 기본적으로 메모리를 많이 잡아먹습니다. 각 해시값에 해당하는 버킷을 할당하거든요.
이 때문에 idx[i] = tmp하면서 메모리 복사에 의한 오버헤드가 원인이 될 수 있을 것 같네요.
게다가 key값이 다양하게 들어온다면 해시충돌도 발생할 수 있구요.
또, 해싱하는데 걸리는 시간도 생각해보면.. 느려질만한 이유가 있을 듯 합니다.
(제 추측이고 정확하지는 않습니다!)
그럼 이전 코드의 unordered_map과 set을 사용하는 코드로 돌아갑시다.
문제를 다시 읽어봅시다. 바이러스의 번호는 1부터 K까지로만 입력된다고 합니다.
그럼 map, unordered_map이 아니라 그냥 배열로 선언해도 되지 않을까요?
배열로 선언하면 해싱이나 해시충돌로 인한 오버헤드가 줄어들 것입니다.
그럼 바꿔서 제출해볼까요?
// unordered_map<int,set<pii>> idx;
set<pii> idx[1'001];
실행시간이 60ms로 줄었습니다!
기존 200ms에서 60ms로 아주 유의미하게 줄었지만, 더 줄여봅시다!
최적화하면서 idx[i]의 원소를 삽입 삭제할 일이 생길까봐 set을 썼었는데, 이젠 set을 쓸 이유가 없어보입니다.
set이아니라 동적 배열인 vector로 바꿔봅시다.
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define X first
#define Y second
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int board[202][202];
vector<pii> idx[1'001];
int n,k;
void spread(){
for(int i=1;i<=k;i++){
vector<pii> tmp;
for(auto cur : idx[i]){
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(board[nx][ny]!=0) continue;
board[nx][ny] = i;
tmp.push_back({nx,ny});
}
}
idx[i] = tmp;
}
}
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>>board[i][j];
idx[board[i][j]].push_back({i,j});
}
int s,x,y; cin>>s>>x>>y;
for(int i=0;i<s;i++){
spread();
}
cout<<board[x-1][y-1]<<'\n';
}
제출했더니 실행시간이 24ms로 줄었습니다!
아직 끝난게 아닙니다! 거의 다 왔어요!
방금 vector로 바꿨는데 굳이 vector를 써야할까요?
탐색은 vector의 앞에서부터 진행하고, 바이러스가 새로 위치한 좌표는 idx[i]의 모든 좌표가 탐색이 완료 된 후에 진행합니다.
엇.. 앞에서부터 진행하고... 새로운건 앞이 다 완료되고 진행한다고..? 어떤 자료구조가 떠오르지 않나요?
저는 큐가 떠올랐습니다. queue를 이용하여 더 최적화 할 수 있어 보입니다.
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define X first
#define Y second
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int board[202][202];
queue<pii> idx[1'001];
int n,k;
void spread(){
for(int i=1;i<=k;i++){
int cnt = idx[i].size();
while(cnt--){
pii cur = idx[i].front(); idx[i].pop();
for(int dir=0;dir<4;dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx<1||nx>n||ny<1||ny>n) continue;
if(board[nx][ny]) continue;
board[nx][ny] = i;
idx[i].push({nx,ny});
}
}
}
}
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>>board[i][j];
idx[board[i][j]].push({i,j});
}
int s,x,y; cin>>s>>x>>y;
for(int i=0;i<s;i++){
spread();
}
cout<<board[x-1][y-1]<<'\n';
}
vector를 queue로 바꿔주면서 tmp를 이용하여 vector를 복사하는 시간이 사라졌는데..
실행시간은 28ms로 늘어났네요...?
queue STL에서 내부적으로 추가적인 연산이 있나봅니다. 이로 인해 실행시간이 늘어난 것으로 보이네요.
그럼 다시 고민해봅시다...
방금 큐를 도입한 것과 같은 맥락입니다.
우리는 각각의 바이러스 번호마다 큐를 나누어서 관리하고있습니다.
그런데 문제상황을 보면. 바이러스도 번호 순서대로 퍼집니다.
예제 입력 1번에서,
1번 바이러스가 먼저 퍼지고, 퍼지면서 1번이 새로 차지한 좌표는 2번, 3번 바이러스가 퍼진 후에 퍼지기 시작할 겁니다.
마찬가지로 이후 2번 바이러스가 퍼지고, 2번이 새로 차지한 좌표는 3번이 퍼지고, 위의 1번의 새 좌표가 퍼진 후에야 퍼질 것입니다.
정리하면, 1번부터 K번까지 바이러스가 퍼진 후에, 1번부터 K번 바이러스가 새로 차지한 좌표에서 퍼지게 됩니다.
앞에서부터 퍼지고, 새 좌표는 뒤에 넣어주고...
이걸 큐로 관리할 수 있지 않을까요?
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define X first
#define Y second
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int board[202][202];
vector<pii> idx[1'001];
queue<pii> q;
int n,k;
void spread(){
for(int i=q.size();i;i--){
pii 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(board[nx][ny]) continue;
board[nx][ny] = board[cur.X][cur.Y];
q.push({nx,ny});
}
}
}
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>>board[i][j];
idx[board[i][j]].push_back({i,j});
}
for(int i=1;i<=k;i++){
for(pii a: idx[i]) q.push(a);
}
int s,x,y; cin>>s>>x>>y;
while(s--){
spread();
}
cout<<board[x-1][y-1]<<'\n';
}
최종적인 최적화 모습입니다.위 코드의 실행시간은 4ms입니다.여태 했던 것과 마찬가지로 idx에 좌표를 저장하고, 바이러스 번호 순서대로 큐에 삽입합니다. (같은 바이러스 간 탐색 순서는 중요하지 않습니다!)
이후 q에 저장된 정보를바탕을 spread를 s번 진행해줍니다.
이제 시간복잡도에 대해서 생각해봅시다.spread 함수의 실행시간은 결국 큐의 크기에 의존하게 되는데, 큐의 크기가 들쭉날쭉해서 예상하기가 어려워보입니다.
큐에 들어가는 좌표에 대해서 생각해봅시다.큐에 한번 들어갔다 나온 좌표는 다시 q에 들어갈 수 있을까요?답은 NO입니다.큐의 들어간 좌표가 (i,j)라고 하면 (i,j)를 처리할 때, board[i][j]에는 바이러스의 번호가 저장되게 됩니다.board에 0이 아닌 다른 값이 저장되어 있는 경우 if문에 걸려 큐에 결코 다시 삽입되지 않습니다.
따라서 큐의 최대크기는 n*n이 되고, 이 경우에 s에 상관없이 시간복잡도는 O(n*n)이 됩니다.
그럼 입력받는데에 O(n*n),바이러스의 좌표를 큐에 저장하는데에 O(n*n),s번 spread하는데에 O(n*n).
따라서 전체 시간복잡도는 O(n*n)이고,n은 최대 200이므로 1초안에 충분히 동작하게 됩니다.
맨처음 말했던, spread를 해도 board 상태가 바뀌지 않으면 정지시키는 방법은 적용하지 않았습니다.spread가 연산후 q에 들어간게 있다면 return 1, 그렇지 않다면 return 0을 받아서 while문을 break해주는 식으로 코드를 짤 수 있지만, 실행시간은 위 코드와 마찬가지로 4ms로 나오더라구요..
더 최적화하려면... STL을 사용하지않고, 큐를 직접 구현한다거나... vector가 아닌 정적 배열을 사용하면 더 빨라질 것 같긴 합니다만, 크게 의미가 있어 보이지는 않네요.
수고하셨습니다!
우리는 꽤 긴 여정을 거쳤습니다.
저도 이렇게 글을 많이 쓴건 처음인 것 같네요..
TLE → TLE → 776ms → 208ms → 344ms → 60ms → 24ms → 28ms → 4ms
총 9단계에 걸쳐서 문제풀이 및 최적화를 진행하였습니다.
그 결과, 가장 처음 AC를 맞았던 776ms 풀이에서 최종적으로 20배 가량 빠른 4ms 풀이를 찾아냈습니다.
제 최종 코드보다 더 빠른 코드도 존재합니다.
실제로 0ms에 통과하는 코드를 제출하신분들도 많구요. (전 아무리 해도 4ms가 최선일 것 같습니다..)
문제에 있는 그대로 구현해봤다가 TLE도 나보고,
불필요한 연산을 줄여 AC를 받는 풀이를 만들고,
더 빠를 줄 알고 제출했던 코드가 원래보다 더 느린 시행착오도 겪었고,
지금 코드를 왜 이렇게 짰는지, 지금 쓰는 자료구조가 정말 최선인지에 대해서도 고민해보고,
계속해서 최적화하여 마침내 충분히 빠른 풀이를 도출해 냈습니다.
요즘 개인적으로 코드 최적화와 관련해서 많이 생각해보고 공부하고 있습니다.
아는만큼 보인다고, 평소라면 그냥 AC받고 넘겼을 문제였지만, 여러 방면에서 최적화를 시도해보니 제법 만족스러운 결과를 냈네요.
solved.ac 랜덤 마라톤으로 만난 골드5 문제이고, 그렇게 어려운 문제는 아니지만, 그런 문제에서도 이렇게 생각해 볼 것이 많다는 것을 알 수 있었습니다.
부족한 실력이지만 여기까지 읽으시느라 고생 많으셨습니다. 재밌었습니다!