[BFS/DFS] 백준 16234번 '인구 이동' (Python)

<문제 링크>

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

---

<문제 풀이>

0. 해당 나라를 q에 추가하고 union = 연합번호로 변경.

0. 현재 연합 인구수랑 연합 국가 수 변수도 추가

0. q가 빌 때까지 상하좌우 나라 확인. 옆의 나라와 인구차이가 조건에 맞으면 연합에 추가

0. q가 다 끝나면 연합 국가끼리 인구 분배

1. visited 처럼 해당 나라가 아직 처리되지 않았다면(union==-1) process 함수 적용.. 후 연합 번호 증가

2. 만약 인구 이동이 끝나면 종료

3. 횟수 증가

 

<코드>

#이취코 답
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,1,0,0]
dy = [0,0,1,-1]

result = 0

def process(x,y,index):
	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()
        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:
            	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)

 

<고쳐야 할 점>

• 문제 해결 능력 키우기...
• 문제 익숙해지기 
• 복습 알고리즘