1. 문제
-
백준 16234 문제와 동일
- 링크 -
국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하면, 두 나라가 공유하는 국경선을 하루 동안 연다.
-
연합 각 칸의 인구수 (연합의 인구수 / 칸의 개수) , 소수점은 버린다.
-
연합 해체하고, 국경선을 닫는다.
-
인구 이동이 며칠 동안 발생하는지 구하라.
입출력 조건 및 예시
2. 아이디어
- BFS함수 정의 : BFS를 이용해서 연합이 가능한지 확인하고 연합국가 좌표를 모은다.
- 모든 국가를 돌면서 BFS를 실행하고, 연합가능한 국가에 인구를 배분한다.
- 이것을 while문을 이용해서 가능할 때까지 반복한다.
- 한번 전체국가가 연합가능한지 확인할 때마다, 방문확인용 리스트를 새롭게 리셋한다.
3. 예제 코드 (pypy3만 통과 가능)
## 입력
n, l, r = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
## bfs 만들기
from collections import deque
dx = [1, -1, 0, 0]
dy = [0,0, -1, 1]
def bfs(x,y):
q = deque()
q.append((x,y))
united = []
united.append((x,y)) # 연합 가능한 국가 좌표 모으기
con_count = 1 # 나라 수
con_pop = graph[x][y] # 나라 인구
while q :
x,y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx <n and 0<=ny <n and visited[nx][ny] == 0 :
if l <= abs(graph[nx][ny] - graph[x][y]) <= r: # 연합 가능하면
visited[nx][ny] = 1 # 방문처리
q.append((nx,ny))
united.append((nx,ny))
con_count += 1 # 나라 수 추가
con_pop += graph[nx][ny] # 나라 인구수 추가
return united, con_count, con_pop # 나라 좌표, 나라 수, 나라 인구수
## 메인
answer = 0
while True :
flag = False
visited = [[0]*n for _ in range(n)] # 방문 만들기
for i in range(n):
for j in range(n): # 지도 전체 탐색
if visited[i][j] == 0 : # 미방문이면
visited[i][j] = 1
country , country_num , country_population = bfs(i,j)
if country_num > 1 : # 연합가능하면
flag = True
even_pop = country_population//country_num # 인구 배분
for a, b in country :
graph[a][b] = even_pop # 배분된 인구 배분
if flag == False:
break
answer += 1 # 횟수 상승
# 정답 출력
print(answer)4. 배운점
- BFS 응용, 기본 BFS에서 연산을 추가한 것 학습
참조
- 이것이 취업을 위한 코딩테스트다. with 파이썬
성장하는 데이터 분석가