문제 링크
16234번: 인구 이동
첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100) 둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100) 인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.
www.acmicpc.net
문제 풀이
- 현재 국가 위치에서 상하좌우의 국가의 인구수 차이를 계산하고, 하나라도 그 차이가 l이상 r이하일 때, 두 국가는 문이 열려 있으므로 인구 이동을 하게 된다.
- 인접한 국가 사이 중 문이 열려 있는 국가를 대상으로 반복 탐색한 후 해당 국가 전체에 대해 인구 이동을 시작한다.
- (1,1) 위치부터 (n,n) 위치까지의 국가에 대해서 인구 이동이 모두 진행되었다면, 또다시 (1,1) 위치부터 인접 국가와의 인구수 차이를 계산하여 더 이상 l이상 r이하의 차이가 나오지 않을 때까지 진행하면 된다.
전체 코드
import sys
from collections import deque
input = sys.stdin.readline
# 인구 이동을 하게되는 국가들
def mig(x, y):
queue = deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
visited[x][y] = True
location.append((x, y))
country.append(popul[x][y])
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
if l <= abs(popul[x][y] - popul[nx][ny]) <= r:
visited[nx][ny] = True
queue.append((nx, ny))
# 인구 이동 후의 각 나라의 바뀐 인구 수
def check():
total = sum(country) // len(country)
for x, y in location:
popul[x][y] = total
n, l, r = map(int, input().split())
popul = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
day = 0
while True:
visited = [[False] * n for _ in range(n)]
move = False # 인구 이동이 발생하지 않음
for i in range(n):
for j in range(n):
country = [] # 인구 이동이 발생하는 국가의 인구 수
location = [] # 인구 이동이 발생하는 국가 위치
if not visited[i][j]:
mig(i, j)
# 인구 이동이 발생했을 때
if len(country) > 1:
check()
move = True # 인구 이동이 발생함
if move == False:
break
else:
day += 1
print(day)
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[백준/Python] 2631 줄 세우기 (0) | 2024.04.11 |
---|---|
[백준/Python] 14719 빗물 (0) | 2024.04.09 |
[백준/Pyhon] 14002 가장 긴 증가하는 부분 수열 4 (0) | 2024.04.04 |
[백준/Python] 14891 톱니바퀴 (0) | 2024.04.03 |
[백준/Python] 14502 연구소 (0) | 2024.03.28 |