DFS/BFS) 인구 이동

Yona·2022년 1월 24일

DFS/BFS 백준 알고리즘 이코테

👩‍🎓 이것이 코딩 테스트다

목록 보기

17/27

백준16234
이코테 책 353p

문제

제한

시간 2초 / 메모리 512MB
입력
- 첫째줄: N, L, R
  (1<=N<=50, 1<=L<=R<=100)
- 둘째줄~: 각 나라의 인구수.
  r행 c열에 주어지는 정수는 A[r][c] 값.
  (0<=A[r][c]<=100)
- 인구이동이 발생하는 횟수 <= 2000
출력
- 첫째줄 : 인구이동이 몇 번 발생하는지 출력

상황

상황
- N*N 크기의 땅.
- 각 땅에는 나라가 하나씩 존재.
- r행c열에 있는 나라에는 A[r][c] 명이 살고 있있음
- 인접한 나라 사이에는 국경선 존재
- 모든 나라의 크기는 1*1 (모든 국경선은 정사각형 형태)
각 나라의 인구수가 주어졌을때, 인구이동이 몇 번 발생하는지 구하시오
더 이상 인구 이동이 없을때까지 지속된다.
- 국경선을 공유하는 두 나라의 인구차이가 L이상 R이하면, 두 나라가 공유하는 국경선을 하루동안 연다.
- 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면 인구이동 시작
- 국경선이 열려있어 인접칸만을 이용해 이동할 수있으면, 그 나라를 오늘 하루동안은 '연합'
- 연합 이루고 있는 각 칸의 인구수는 (연합인구수) / (연합을 이루고 있는 칸의 갯수). (N빵한다는 뜻이구만) 소숫점 버림
- 연합 해체하고 모든 국경선 닫는다

풀이

처음 든 생각

BFS/DFS로 덩어리구하는 문제구만..

모든 국경선을 다 연다.
연합국 덩어리 기준(BFS 사용)으로 연합국간 인구를 N빵하여 초기화한다.
열 국경선이 없을때 멈춘다.

이렇게 하면 안되나

풀이

전형적인 DFS/BFS 문제

풀이아이디어

모든 국경선을 다 연다.
연합국 덩어리 기준(BFS 사용)으로 연합국간 인구를 N빵하여 초기화한다.
열 국경선이 없을때 멈춘다.

위에서 처음 생각한게 맞았다.

코드

from collections import deque

# 땅의 크기(N), L, R 값을 입력받기
n, l, r = map(int, input().split())

# 전체 나라의 정보(N*N)을 입력받기
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))
	# 너비 우선 탐색(BFS)를 위한 큐 자료구조 정의
	q = deque()
	q.append((x,y))
	union[x][y] = index # 현재 연합의 번호 할당
	summary = graph[x][y] # 현재 연합의 전체 인구 수
	count = 1 # 현재 연합의 국가 수

	# 덩어리 찾기 = 큐가 빌때까지 반복 (BFS)
	while q :
		x, y = q.popleft()
		# 현재 위치에서 4가지 방향을 확인하여
		for i in range(4) :
			nx = x + dx[i]
			ny = y + dy[i]
		# 바로 옆에 있는 나라를 확인하여
		if 0 <= nx < n and 0 <= ny < n and union[nx][ny] == -1 :
			# 옆에 있는 나라와 인구 차이가 L명 이상, R명 이하라면
			if l <= abs(graph[nx)[ny] - graph[x][y]) <= 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)