[백준 16234번] 인구 이동 - python

문제 링크

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

16234번: 인구 이동

 

풀이 

bfs로 풀이 

while 문을 통해 아래 과정을 반복 

1. 아직 방문하지 않은 나라가 있다면 bfs를 실행하여 인구 차이가 l이상 r 이하인 나라에 대해 국경을 연다.

- bfs를 통해 탐색하여, 이동할 수 있는 나라가 있다면

해당 위치를 set에 저장, 방문표시, 인구 수 저장, 나라 수 +

- 탐색이 끝난 후, 만약 이동할 수 있는 나라가 없다면 false 리턴

- 이동할 수 있는 나라가 있다면 tmp에 저장된 나라들에 대해 인구수 / 나라수 값으로 설정 

 

2. check 변수를 통해 bfs가 false, 즉 더이상 이동할 수 없다면 True로 설정하여 while문을 중단한다. 

 

3. 일수 cnt + 1 

from collections import deque

def bfs(x, y):
    q = deque()
    cnt = 1
    tmp = [[x,y]]
    total = graph[x][y]
    q.append((x,y))
    visited[x][y] = True

    while q:
        x ,y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx <0 or nx >= n or ny <0 or ny>=n:
                continue

            if l <= abs(graph[x][y]-graph[nx][ny]) <= r and not visited[nx][ny]:
                visited[nx][ny] = True
                total += graph[nx][ny]
                cnt += 1
                tmp.append((nx,ny))
                q.append((nx,ny))
	
    # 이동안함 
    if cnt == 1:
        return False

    total = total // cnt
    for a, b in tmp:
        graph[a][b] = total

    return True

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]

cnt = 0

while True :
    visited = [ [False] * n for _ in range(n)]

    check = False
    for i in range(n):
        for j in range(n):
            if not visited[i][j] :
                if bfs(i,j):
                    check = True
	# 더이상 이동 못함 
    if not check:
        break
        
    cnt +=1

print(cnt)