[백준] 인구 이동(BFS)

문제보기

🔑문제해결과정

1. 모든 곳을 BFS로 방문하여 연합을 진행한다.
2. l <= 인구차이 <= r 이면, 연합을 진행한다.
   • 연합 국가 간 인구수 = (연합의 인구수) / 연합을 이루고 있는 칸의 개수
   • 연합국가 = union[(i, j)]로 선언.
   • 총 연합된 국가수 = cnt = graph[i][j]

✏️전체 코드

import sys
import math
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 = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(i, j):
    q= deque()
    q.append((i, j))
    visited[i][j] = True
    # 국가 연합
    union = [(i, j)]
    # 총 연합된 국가수
    cnt = graph[i][j]
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if l <= abs(graph[nx][ny] - graph[x][y]) <= r:
                    union.append((nx, ny))
                    visited[nx][ny] = True
                    q.append((nx, ny))
                    cnt += graph[nx][ny]
    for x, y in union: # (연합의 인구수) / (연합을 이루고 있는 칸의 개수)
        graph[x][y] = math.floor(cnt / len(union))
    return len(union)

# 날짜를 출력
day = 0
while True:
    visited = [[False] * n for _ in range(n)]
    flag = False #인구이동 유무를 판별하기 위한 플래그
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                if bfs(i, j) > 1:
                    flag = True
    if not flag:
        break
    day += 1
print(day)