백준(boj) 16234_인구 이동 (파이썬, c++)

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

풀이

---

인구이동이 일어나지 않을 때까지 반복하는 문제이다.

인구이동이란 인접한 곳의 인구 차이가 L 이상, R 이하이면 국경선이 열리는데, 국경선이 열린 곳은 동맹국이 되고, 동맹국들은 (동맹국 총인구수/동맹국의 수)로 인구가 변한다.

어느 곳을 시작점으로 잡아도 조건상 동맹국이 되는 곳들은 같으므로, 2중 포문으로 모든 곳을 확인하는데, 방문하지 않은 곳들(아직 동맹국이 안된or안될 곳들)만 순서대로 확인한다. 방문하지 않은 곳은 4방향 탐색을 하면서 L <= abs(차이) <= R인 곳이 있으면 총합(SUM)과 개수(cnt)를 더하고, 좌표를 기록해둔다.

더 이상 들를 곳이 없으면, cnt가 2이상인지 확인해보고(1개면 자기 자신만이라 인구이동이 일어나지 않음) 기록해둔 좌표들의 값을 SUM/cnt로 갱신해준다. 이때, cnt가 2이상이면 인구이동이 일어난 것이므로 flag를 사용해서 표시해두면, 모든 곳을 확인해 준 뒤 flag를 보고 인구 이동이 일어났나 확인해 줄 수 있다.

python3 (Pypy3 제출)

from sys import*
from collections import*
input = stdin.readline
n,l,r = map(int,input().split())
a=[list(map(int,input().split()))for _ in range(n)]
res = 0; time=0
dd=[(-1,0),(0,1),(1,0),(0,-1)]
while 1:
    f = 0
    check=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not check[i][j]:
                q=deque(); SUM=a[i][j]; cnt=1; temp=[]
                q.append((i, j))
                temp.append((i, j))
                check[i][j]=1
                while q:
                    x, y = q.popleft()
                    for dx, dy in dd:
                        nx, ny = x+dx, y+dy
                        if nx<0 or ny<0 or nx>n-1 or ny>n-1 or check[nx][ny]: continue
                        if l <= abs(a[nx][ny]-a[x][y]) <= r:
                            cnt += 1
                            temp.append((nx, ny))
                            SUM += a[nx][ny]
                            q.append((nx, ny))
                            check[nx][ny]=1
                if cnt >= 2:
                    f=1
                    for x, y in temp:
                        a[x][y] = SUM//cnt
    if not f: break
    time+=1
print(time)

C++

#include<cstdio>
#include<queue>
#include<memory.h>
#include<stdlib.h>
#include<vector>
using namespace std;
typedef pair<int, int> P;
const int SIZE = 101;
int a[SIZE][SIZE], visit[SIZE][SIZE];
int n, L, R;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
int check(int i, int j, int num){
    int cnt=1, sum=a[i][j];
    vector<P> v;
    queue<P> q;
    q.push({i, j});
    v.push_back({i, j});
    visit[i][j]=num;
    while(!q.empty()){
        int x, y;
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int nx, ny;
            nx = x+dx[i], ny = y+dy[i];
            if(nx<0 || ny<0 || nx>n-1 || ny>n-1 || visit[nx][ny] || abs(a[nx][ny]-a[x][y])<L
            || abs(a[nx][ny]-a[x][y])>R) continue;        //abs :: stdlib.h
            visit[nx][ny] = num;
            q.push({nx, ny});
            cnt++;
            sum+=a[nx][ny];
            v.push_back({nx, ny});
        }
    }
    if(cnt>1){
        int avg = sum/cnt;
        for(int i=0; i<v.size(); i++){
            int x, y;
            x = v[i].first;
            y = v[i].second;
            a[x][y] = avg;
        }
        return avg;
    }
    return -1;
}
int main(){
    scanf("%d %d %d", &n, &L, &R);
    int res=0;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++){
            scanf("%d", &a[i][j]);
        }
    while(1){
        bool canMove = false;
        int avg;
        int num=1;
        memset(visit, 0, sizeof(visit));
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++){
                if (!visit[i][j]){
                    avg = check(i, j, num);
                    if(avg != -1){
                        canMove = true;
                    }
                    num++;
                }
            }
        if(!canMove){
            printf("%d", res);
            break;
        }
        res++;
    }
    return 0;
}

고찰

---

.