[Python] 백준 16234번 : 인구 이동

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

16234번: 인구 이동

---

💡 문제 풀이

BFS를 기반으로 한 구현 문제이다.

 

문제에서 요구하는 답은 인구 이동이 몇 번 일어났는지가 아니라 인구 이동이 일어난 날짜이다.

따라서, 단순하게 몇번 실행되었는지 보다 날짜를 기준으로 카운트하는 게 중요하다

✔️ 느낀 점

중요한 점을 놓쳐서 코드를 깨작깨작 계속 수정햇던 문제이다. 

시간 복잡도는 생각한대로 해결되었다!

💻 코드

import sys ; input = sys.stdin.readline
from collections import deque

n,l,r = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]

dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(a,b):
    q = deque([[a, b]])
    union = [(a,b)]
    
    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))
                    union.append((nx,ny))
                    
    return union

result = 0
while 1:
    visited = [[0] * (n+1) for _ in range(n+1)]
    flag = 0
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0:
                visited[i][j] = 1
                country = bfs(i,j)
                if len(country) > 1:
                    flag = 1
                    number = sum([graph[x][y] for x, y in country]) // len(country)
                    for x,y in country:
                        graph[x][y] = number
    if flag == 0:
        break
    result += 1
    
print(result)