인구이동

인구이동

Solution

BFS

1. 모든 나라를 돌면서 국경선을 공유할 나라를 묶는다.
2. 국경선을 공유한 나라의 인구수를 업데이트한다.
3. 인구이동이 없을 때까지 반복한다.

2019.10.19

C++ 풀이

#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

const int MAX = 55;
int map[MAX][MAX][2];
bool check[MAX][MAX];
pair <int,int> rememMap[MAX*MAX];
int N,L,R;
queue <pair<int,int>> myQ;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int BFS(int y,int x,int nowIdx,int nextIdx){
    int count = 0;
    int sumMap = map[y][x][nowIdx];
    check[y][x]=true;
    myQ.push(make_pair(y,x));
    rememMap[count++] = make_pair(y,x);

    while(!myQ.empty()){
        int Qsize = myQ.size();
        for(int i=0;i<Qsize;i++){
            pair <int,int> current = myQ.front();
            myQ.pop();
            int currentValue = map[current.first][current.second][nowIdx];
            for(int dir=0;dir<4;dir++){
                int yy = current.first+dy[dir];
                int xx = current.second+dx[dir];
                if(yy>=0&&xx>=0&&yy<N&&xx<N){
                    int adjValue = map[yy][xx][nowIdx];
                    int dist = currentValue-adjValue;
                    if(dist<0) dist = -dist;
                    if(check[yy][xx]==false && dist>=L && dist<=R){
                        check[yy][xx] = true;
                        sumMap += adjValue;
                        rememMap[count++] = make_pair(yy,xx);
                        myQ.push(make_pair(yy,xx));
                    }
                }
            }
        }
    }

    int nextValue = sumMap/count;
    for(int i=0;i<count;i++){
        int yy = rememMap[i].first;
        int xx = rememMap[i].second;
        map[yy][xx][nextIdx] = nextValue;
    }

    if(count==1) return 0;
    else return 1;
}

int getResult(){
    int result = 0;

    while(1){
        result++;
        int now = (result+1)%2;
        int next = result%2;
        int move = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(check[i][j]==false){
                    move += BFS(i,j,now,next);
                }
            }
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                check[i][j] = false;
            }
        }
        if(move==0){
            result--;
            break;
        }
    }

    return result;
}

int main(){
    scanf("%d %d %d",&N,&L,&R);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%d",&map[i][j][0]);
        }
    }
    printf("%d\n",getResult());

    return 0;
}

2021.04.14

Python 풀이

import sys
sys.stdin = open('input.txt', 'r')

from collections import deque

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

def BFS(myMap, visited, N, y, x, L, R):
    myQ = deque()
    retList = []
    myQ.append((y, x))
    retList.append((y,x))
    visited[y][x] = True
    retVal = myMap[y][x]

    # BFS
    while myQ:
        here = myQ.popleft()
        for d in range(4):
            nextY = here[0] + dy[d]
            nextX = here[1] + dx[d]
            if nextY >=0 and nextY < N and nextX >=0 and nextX < N:
                if not visited[nextY][nextX]:
                    dif = abs(myMap[here[0]][here[1]] - myMap[nextY][nextX])
                    if dif >= L and dif <= R:
                        visited[nextY][nextX] = True
                        myQ.append((nextY, nextX))
                        retList.append((nextY, nextX))
                        retVal += myMap[nextY][nextX]

    # 국경선을 공유한 나라가 없으면 인구이동 없음(False)을 리턴한다.
    if len(retList) == 1:
        return False

    # 국경선을 공유한 나라의 인구수 업데이트.
    for location in retList:
        myMap[location[0]][location[1]] = int(retVal / len(retList))

    return True

def solution(inputMap, N, L, R):
    cnt = -1

    # 인구이동이 없을 때까지 반복
    while True:
        cnt += 1
        visited = [[False for _ in range(N)] for _ in range(N)]
        CanMove = False

        # 모든 나라를 돌면서 국경선을 공유할 나라 탐색
        # 탐색한 후 바로 map에 업데이트 해준다
        # visited로 검증을 하기 때문에 업데이트한다고해서 탐색에 영향주지 않음.
        for i in range(N):
            for j in range(N):
                if not visited[i][j]:
                    if BFS(inputMap, visited, N, i, j, L, R):
                        CanMove = True

        if not CanMove:
            break

    return cnt

N, L, R = map(int, input().split())
inputMap = [list(map(int, input().split())) for _ in range(N)]
print(solution(inputMap, N, L, R))