16234 인구 이동

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

16234번: 인구 이동

또다시 삼성의 벽을 느끼게 된 순간이다. 솔직히 문제 자체는 크게 어렵지 않지만 테크닉이 부족해서 시간이 좀 걸렸다. 

 

처음 작성한 코드인데, 80%에서 시간 초과가 걸렸다. 아무리 봐도 답이 나오지 않아 Chat GPT에게 도움을 청했더니 board를 갱신하는 부분을 배열을 하나하나 돌면서 하지 않고, BFS를 사용하면 시간 초과 없이 해결할 수 있었다. 

#include <bits/stdc++.h>
using namespace std;
int N,L,R,idx,days;
int board[53][53];
int vis[53][53];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>L>>R;
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			cin>>board[i][j];
	
	bool imigrated=true;
	while(imigrated){
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				vis[i][j]=0;
		imigrated=false; idx=0;
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(vis[i][j]!=0) continue;
				idx++;
				queue<pair<int,int>> Q;
				Q.push({i,j}); vis[i][j]=idx;
				while(!Q.empty()){
					auto cur=Q.front(); Q.pop();
					for(int dir=0;dir<4;dir++){
						int ny=cur.first+dy[dir];
						int nx=cur.second+dx[dir];
						if(ny<0||nx<0||ny>=N||nx>=N) continue;
						int diff=abs(board[cur.first][cur.second]-board[ny][nx]);
						if(diff<L||diff>R||vis[ny][nx]!=0) continue;
						Q.push({ny,nx}); vis[ny][nx]=idx;
					}
				}
			}
		}
		for(int num=1;num<=idx;num++){
			int sum=0,cnt=0;
			for(int i=0;i<N;i++){
				for(int j=0;j<N;j++){
					if(vis[i][j]==num){
						cnt++; sum+=board[i][j];
					}
				}
			}
			if(cnt>1){
				imigrated=true;
				int val=sum/cnt;
				for(int i=0;i<N;i++){
					for(int j=0;j<N;j++){
						if(vis[i][j]==num){
							board[i][j]=val;
						}
					}
				}
			}
		}
		if(imigrated) days++;
	}
	cout<<days;
 	return 0;                                 
}

 

통과된 코드이다.

#include <bits/stdc++.h>
using namespace std;
int N,L,R,idx,days;
int board[53][53];
int vis[53][53];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>L>>R;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin>>board[i][j];
    
    bool imigrated=true;
    while(imigrated){
        memset(vis, 0, sizeof(vis)); // 방문 여부 배열 초기화
        imigrated=false; idx=0;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(vis[i][j]!=0) continue;
                idx++;
                queue<pair<int,int>> Q;
                Q.push({i,j}); vis[i][j]=idx;
                int total_population = board[i][j];
                int total_countries = 1;
                while(!Q.empty()){
                    auto cur=Q.front(); Q.pop();
                    for(int dir=0;dir<4;dir++){
                        int ny=cur.first+dy[dir];
                        int nx=cur.second+dx[dir];
                        if(ny<0||nx<0||ny>=N||nx>=N) continue;
                        int diff=abs(board[cur.first][cur.second]-board[ny][nx]);
                        if(diff<L||diff>R||vis[ny][nx]!=0) continue;
                        Q.push({ny,nx}); 
                        vis[ny][nx]=idx;
                        total_population += board[ny][nx];
                        total_countries++;
                    }
                }
                int new_population = total_population / total_countries;
                if (total_countries > 1) { // 인구 이동이 있었으면
                    imigrated = true;
                    Q.push({i,j}); // 다시 큐에 넣고
                    while(!Q.empty()){ // 방문한 곳들의 인구를 모두 변경
                        auto cur=Q.front(); Q.pop();
                        board[cur.first][cur.second] = new_population;
                        for(int dir=0;dir<4;dir++){
                            int ny=cur.first+dy[dir];
                            int nx=cur.second+dx[dir];
                            if(ny<0||nx<0||ny>=N||nx>=N) continue;
                            if(vis[ny][nx]==idx) {
                                Q.push({ny,nx}); // 방문 여부를 체크하지 않으면 큐에 넣을 때 여러 번 중복으로 들어갈 수 있음
                                vis[ny][nx] = -1; // 방문 표시를 함으로써 중복 방문을 방지
                            }
                        }
                    }
                }
            }
        }
        if(imigrated) days++;
    }
    cout<<days;
    return 0;                                 
}