[백준 / Python] 16234번 : 인구 이동

문제 링크:

문제 이해

---

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 열고 인구 이동을 시작한다(연합).
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다(소숫점은 버린다).

• 인구 이동이 끝나면 국경선을 닫는다. 위 방법에 의해 인구 이동이 없을 때까지 반복된다.
  
  
  

• 최종적으로 구해야 하는 것: 모든 국가가 연합을 이룰 때까지 이동한 날짜(일) 수
• 중간 과정으로 구해야 하는 것:
  1. 각 시점에서 연합을 이루는 국가
  2. 연합을 이룬 뒤 변화되는 인구 수
     
     
     
     
     
     

해결 전략

---

1. BFS로 인접 국가와 연합을 이루는 그룹 찾기(dict 저장).
2. 국가 연합 정보를 바탕으로 인구 이동 계산, 국가 인구 정보 업데이트
3. 국가 간 인구 수가 조건을 만족하지 않을 때 까지 반복(종료 조건)
   
   
   
   
   
   

구현 코드, 풀이

---

import collections

#    동  남  서  북
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def bfs_union(x, y, dist, results, cnt):

    contry_1 = contry[x][y]

    q = collections.deque([(x, y, contry_1)])
    dist[x][y] = 0
    results[cnt].append([x, y, contry_1])

    while q:
        x, y, population = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            
            if nx < 0 or nx >= N or ny < 0 or ny >= N or dist[nx][ny] != -1:
                continue

            neighbor_popu = contry[nx][ny]
            diff_pop = abs(neighbor_popu - population)

            if diff_pop >= L and diff_pop <= R:
                dist[nx][ny] = 0 
                q.append((nx, ny, neighbor_popu))
                results[cnt].append([nx, ny, neighbor_popu])
          
    cnt += 1
    return results, dist, cnt

def move_pop(union_results, contry):

    for key, value in union_results.items():
        if len(value) > 1:
            entire = [pop for i, j, pop in value]
            devide_pop = int(sum(entire) / len(value))

            for i, j, pop in value:
                contry[i][j] = devide_pop
          
    return contry

# input
N, L, R = map(int, input().split())
contry = [list(map(int, input().split())) for _ in range(N)]

if __name__ == '__main__':
    day = 0
    iter = True

    while iter: 
        union_results = collections.defaultdict(list)
        cnt = 0
        dist = [[-1] * N for _ in range(N)]
        for i in range(N):
            for j in range(N):
                if dist[i][j] == -1:
                    union_results, dist, cnt = bfs_union(i, j, dist, union_results, cnt)

        if len(union_results) == N * N:
            print(day)
            iter = False
        else:
            day += 1
            move_pop(union_results, contry)

1. main 블록:
   • 초기 입력을 받고, 이동 횟수를 나타내는 day 변수를 초기화함.
   • 반복문안에서 bfs_union 함수(2.)를 통해 국경을 연 상태로 간주되는 연합을 찾고, 인구 이동을 실행한다. 인구이동은 move_pop 함수를 통해 반영한다.
   • 모든 국가에서 연합이 더 이상 일어나지 않을 때 까지 반복한다. 반복이 종료된 후에는 이동한 날짜를 출력.
2. bfs_union 함수:
   • queue를 정의하고, 시작점인 (x, y)를 받아와서 너비 우선 탐색(BFS)을 사용하여 해당 국가와 연결된 모든 국가를 찾기 위해 4방향으로 탐색을 시작한다.
   • 조건에 맞는, 연결된 국가를 찾으면 해당 국가의 위치와 인구를 results에 추가하고, 이동 거리를 dist에 기록한다.
   • 모든 국가를 찾은 후에는 결과와 이동 거리, 그리고 다음 연합을 구분하기 위한 cnt를 반환한다.
3. move_pop 함수:
   • 연합된 국가에 대한 결과를 바탕으로 이동된 모든 인구를 국가에 반영한다. 각 연합에 속한 국가의 평균 인구수를 구하여 해당 국가에 적용한다.