인구 이동

풀이

  BFS, DFS 모두 가능하다고 생각했고 DFS를 활용했다. N*N 그래프를 2중 반복문을 통해 탐색하면서 각각의 지점에서 주어진 조건(인구 이동)에 맞게 DFS 탐색하면된다. 주어진 조건을 만족하면 리스트에 각 지점의 좌표를 저장한다음 dfs가 끝나면 리스트에 저장된 정보들을 토대로 초기화 작업을 진행하면 된다.

import sys
sys.setrecursionlimit(100000)

n, L, R = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]

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


def dfs(x, y):
    for i in range(4):
        new_x = x + dx[i]
        new_y = y + dy[i]

        if 0 <= new_x < n and 0 <= new_y < n and visited[new_x][new_y]==0:
            temp = abs(maps[x][y] - maps[new_x][new_y])
            if L <= temp <= R:
                visited[new_x][new_y] = 1
                stack.append([new_x, new_y])
                dfs(new_x, new_y)


while True:
    visited = [[0] * n for _ in range(n)]
    flag = True
    for i in range(n):
        for j in range(n):
            stack = []

            if visited[i][j] == 0:
                stack.append([i, j])
                visited[i][j] = 1
                dfs(i, j)

                if len(stack) > 1:
                    flag = False
                    avg = sum([maps[x][y] for x, y in stack]) // len(stack)
                    for x, y in stack:
                        maps[x][y] = avg

    if flag:
        break

    count += 1

print(count)

시간복잡도 : O(n^4)