[백준] 16234번 인구 이동 ★★

💡문제접근

• 국경선을 공유하는 두 나라의 인구 차이 조건 참/거짓 여부를 판별하고 연합을 이룰 수 있는 조건이 형성된다면 union 배열에 저장하고 리턴한 union 배열 원소의 개수가 최소 2개 이상이라면 인구 이동을 시켜주면 된다.
• 인구 이동이 며칠동안 발생하는지를 확인하기 위해서 flag 변수를 따로 만들었고 union 배열 원소의 개수가 1개가 나오면 인구 이동이 발생하지 않고 이 때 flag는 False이므로 False일 경우 무한 반복문을 멈추고 인구 이동이 며칠 동안 발생했는지를 출력해주면 되는데 이 과정에서 시간이 많이 소요됐다.

💡코드(메모리 : 34216KB, 시간 : 6548ms)

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

N, L, R = map(int, input().strip().split())
graph = [list(map(int, input().strip().split())) for _ in range(N)]

def BFS(a, b):
    queue = deque()
    union = []
    queue.append([a, b])
    union.append([a, b])
    while queue:
        y, x = queue.popleft()
        dy = [0, 1, 0, -1]
        dx = [-1, 0, 1, 0]
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or ny >= N or nx < 0 or nx >= N:
                continue
            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx]:
                if L <= abs(graph[ny][nx] - graph[y][x]) <= R:
                    visited[ny][nx] = True
                    queue.append([ny, nx])
                    union.append([ny, nx])
    return 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]:
                visited[i][j] = True
                result = BFS(i, j)
                if len(result) > 1:
                    flag = True
                    population = int(sum(graph[y][x] for y, x in result) / len(result))
                    for y, x in result:
                        graph[y][x] = population
    if not flag:
        print(day)
        break
    day += 1

💡소요시간 : 1h