문제
문제 설명
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번 보다 작거나 같은 입력만 주어진다.
입출력 예
| 예시 | 입력 | 출력 |
|---|---|---|
| 예시 1 | 2 20 50 50 30 20 40 | True |
| 예시 2 | 2 40 50 50 30 20 40 | 0 |
| 예시 3 | 2 20 50 50 30 30 40 | 1 |
| 예시 4 | 3 5 10 10 15 20 20 30 25 40 22 10 | 2 |
| 예시 5 | 4 10 50 10 100 20 90 80 100 60 70 70 20 30 40 50 20 100 10 | 3 |
입출력 예 1 설명
초기 상태는 아래와 같다.
https://upload.acmicpc.net/2993ef69-f57e-4d46-a9b3-eb3a05612dc7/-/preview/
L = 20, R = 50 이기 때문에, 모든 나라 사이의 국경선이 열린다. (열린 국경선은 점선으로 표시)
https://upload.acmicpc.net/3e73073e-b68e-478b-90fd-f158f44863b7/-/preview/
연합은 하나 존재하고, 연합의 인구는 (50 + 30 + 20 + 40) 이다. 연합의 크기가 4이기 때문에, 각 칸의 인구수는 140/4 = 35명이 되어야 한다.
https://upload.acmicpc.net/78951cb1-213d-416b-a64d-fb80697af36a/-/preview/
아이디어
- 한 연합 안에 들어가는 나라들을 검사하기 위해 BFS 필요
- 연합에 대한 정보를 저장하는 자료 구조 필요
제출 코드
from collections import deque
n, l, r = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(i, j):
queue = deque()
union = [] #연합에 대한 정보를 저장
queue.append([i, j])
union.append([i, j])
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0:
if l <= abs(graph[x][y] - graph[nx][ny]) <= r:
union.append([nx, ny])
queue.append([nx, ny])
visited[nx][ny] = 1
return union
result = 0
while True:
# 한 번 인구 이동이 지난 뒤에 방문 기록 초기화
# 방문을 저장하는 자료 구조
visited = [[0 for _ in range(n)] for _ in range(n)]
flag = 0
for i in range(n):
for j in range(n):
if visited[i][j] == 0:
# 방문한 적 없을 때 거기에 새로운 연합이 있을지도 모르니 검사
visited[i][j] = True
country = bfs(i, j)
if len(country) > 1:
# 단독 국가가 아닌 연합이 존재한다면
flag = 1
people = sum(graph[x][y] for x, y in country) // len(country)
for x, y in country:
# 인구 이동
graph[x][y] = people
if flag == 0:
# 연합이 더는 존재하지 않는다면
print(result)
break
# 인구 이동이 종료될 때마다 값에 하나씩 추가
result += 1
모범 풀이
from collections import deque
n, l, r = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
result = 0
def process(x, y, index):
# (x, y)의 위치와 연결된 나라 정보를 담는 리스트
united = []
united.append((x, y))
# 너비 우선 탐색을 위한 큐 자료구조 정의
q = deque()
q.append((x, y))
union[x][y] = index # 현재 연합의 번호 할당
summary = graph[x][y] # 현재 연합의 전체 인구 수
count = 1 # 현재 연합의 국가 수
# 너비 우선 탐색 진행
while q:
x, y = q.popleft()
# 현재 위치에서 4가지 방향을 확인
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# 바로 옆에 있는 나라 확인
if 0 <= nx < n and 0 <= ny < n and union[nx][ny] == -1:
# 옆에 있는 나라와 인구 차이가 l이상 r이하일 때
if l <= abs(graph[x][y] - graph [nx][ny]) <= r:
q.append((nx, ny))
# 연합에 추가
union[nx][ny] = index
summary += graph[nx][ny]
count += 1
united.append((nx, ny))
# 연합 국가끼리 인구를 분배
for i, j in united:
graph[i][j] = summary // count
return count
total_count = 0
while True:
union = [[-1] * n for _ in range(n)]
index = 0
for i in range(n):
for j in range(n):
if union[i][j] == -1:
process(i, j, index)
index += 1
if index == n * n:
break
total_count += 1
print(total_count)
if index == n * n: 연합이 하나도 없는 경우 각 나라마다 다른 index를 가져 연합의 개수가 총 n*n 까지 될 수 있음- 따라서 그 이상은 검색할 필요 없이 종료
