https://www.acmicpc.net/problem/16234
시간 2초, 메모리 512MB
input :
- N, L, R (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
- r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)
output :
- 인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.
조건 :
-
국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
-
위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
-
국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
-
연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
-
연합을 해체하고, 모든 국경선을 닫는다.
모든 인접한 나라의 국경선을 연 이후에 인구의 이동이 발생하기 때문에 인접한 두 국가가 바로 인구 이동이 발생하는 것이 아니다.
이번 문제의 경우에는 처음부터 조건을 제한하기는 힘들다. 무한 반복 중에 더 이상 인구 이동이 없다면 break를 걸도록 하는 방식이 나을 것 같다.
날짜별로 나눠서 생각을 해야하는데 그 날짜에 visit 배열을 이용해서 오늘 국경선을 이미 열었는 나라라면 무시하고 그렇지 않은 경우에는 거기서 부터 다시 국경선을 열어야 하는지 확인을 한다.
visit이나 국경선을 여는 나라를 카운팅하는 부분이 헷갈릴 수 있는데 초기 값에서 변화가 없다면 국경선을 열지 않는 다는 것이니 이를 유의 하자.
import sys
dx, dy = [0, 0, -1, 1], [1, -1, 0, 0]
n, l, r = map(int, sys.stdin.readline().split())
data = []
for i in range(n):
data.append(list(map(int, sys.stdin.readline().split())))
day = 0
while True:
visit = [[0] * n for i in range(n)]
value = [0]
cnt = 1
for x in range(n):
for y in range(n):
if visit[x][y] != 0:
continue
temp_value, temp_cnt, visit[x][y] = data[x][y], 1, cnt
temp = [(x, y)]
while temp:
now_x, now_y = temp.pop()
for i in range(4):
nx = now_x + dx[i]
ny = now_y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if visit[nx][ny] == 0 and l <= abs(data[now_x][now_y] - data[nx][ny]) <= r:
visit[nx][ny] = cnt
temp_cnt += 1
temp_value += data[nx][ny]
temp.append((nx, ny))
if temp_cnt > 1:
value.append(temp_value // temp_cnt)
cnt += 1
else:
visit[x][y] = 0
if cnt == 1:
break
for x in range(n):
for y in range(n):
if visit[x][y] == 0:
continue
data[x][y] = value[visit[x][y]]
day += 1
print(day)
