아기 상어
https://www.acmicpc.net/problem/16234
문제
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
오늘부터 인구 이동이 시작되는 날이다.
인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
연합을 해체하고, 모든 국경선을 닫는다.
각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)
인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.
출력
인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.
예제 입력
2 20 50
50 30
20 40
예제 출력
1
풀이
L과 R 사이의 인구차이가 있는 도시 사이의 경계는 허물어지고 평균값으로 통일된다. 한번의 시도마다 모든 경계를 열고 인구를 이동시키면 한번의 인구이동이다. 열리는 경계를 찾기 위해서 BFS을 이용하면 된다.
- (0, 0) 부터 4개의 방향을 검사하고 L과 R사이의 인구차이를 가지고 있으면 queue에 넣어준다.
- 방문한 곳은
visited=True로 표시한다. - queue가 모두 빠져나가서
while len(q)반복문이 끝난다는 것은 인구이동을 할 수 있는 도시를 모두 방문했다는 뜻이다. 반복문이 끝나면 queue를 꺼낼 때마다 append 했던city_list을opened_list에 담는다. 그리고opened_list에 인구이동이 일어난 이후의 (평균)인구수를 함께 저장해놓는다.opened_list = [[[도시1, 도시2, 도시3, ....], 평균인구수], [[도시8, 도시9, 도시10, ...], 평균인구수], ...]와 같은 식으로 국경을 개방할 도시와 평균 인구수가 저장된다. (여기에서 바로 국경개방을 해서 인구이동을 시킬 수 있지만 시간복잡도 때문에 모든 검사가 끝나고 한번에 인구이동을 시킬 것이다.) - (0, 0)부터
visited=False인 곳을 대상으로 위를 반복하면opend_list가 완성된다. - 인구이동을 진행한다.
- 모든 칸을 돌아가면서 위를 반복한다. 탈출 조건은 인구이동할 도시 배열의 크기가 1이하일 경우
flag변수를 이용하여 판단한다.
# -*- coding:utf-8 -*-
from sys import stdin
import collections
N, L, R = list(map(int, stdin.readline().split()))
board = []
for _ in range(N):
board.append(list(map(int, stdin.readline().split())))
q = collections.deque([])
dir4 = [[0, 1], [0, -1], [1, 0], [-1, 0]]
result = 0
while 1:
flag = False
visited = [[False]*N for _ in range(N)]
opened_list = []
for y in range(N):
for x in range(N):
if not visited[y][x]:
q.append([y, x])
visited[y][x] = True
total_popul = 0
city_list = []
while len(q):
now = q.popleft()
total_popul += board[now[0]][now[1]]
city_list.append(now)
for d in dir4:
if 0 <= now[0]+d[0] < N and 0 <= now[1]+d[1] < N and L <= abs(board[now[0]][now[1]] - board[now[0]+d[0]][now[1]+d[1]]) <= R and visited[now[0]+d[0]][now[1]+d[1]] == False:
q.append([now[0]+d[0], now[1]+d[1]])
visited[now[0]+d[0]][now[1]+d[1]] = True
# 인구이동할 도시가 1개 이상이어야지 인구이동이 일어남
if len(city_list) > 1:
flag = True
# 인구 이동할 도시묶음을 나눠서 저장
opened_list.append([city_list, total_popul])
# 인구이동
for city_list in opened_list:
for city in city_list[0]:
board[city[0]][city[1]] = city_list[1] // len(city_list[0])
# for n in range(N):
# print(board[n])
# print('--------------------------')
if not flag:
break;
result += 1
print(result)