[Python] G4 16234 인구 이동

문제 풀이

1. for문으로 땅들을 탐색하며 dfs 탐색을 한다.
2. dfs로 옆땅과의 인구 차이가 L명 이상, R명 이하인 땅들을 탐색해 나간다.
3. 연결된 인구 차이가 L명 이상, R명 이하인 땅의 수와 총 인원 수를 통해 평균 인구 수를 구한다.
4. 연결된 인구 차이가 L명 이상, R명 이하인 땅의 인구 수를 평균 인구 수로 바꿔준다.
5. 이 과정을 옆땅과의 인구 차이가 L명 이상, R명 이하인 땅이 없을 때까지 반복한다.
6. 반복된 횟수를 구한다.

• dfs 반복 횟수 때문에 런타임 에러가 발생했지만 sys.setrecursionlimit(10000)를 통해 limit를 걸어주니 문제가 해결됐다.

정답

import sys
sys.setrecursionlimit(10000)
N, L, R = map(int, input().split())

country = []
total = 0

movex = [0, 1, 0, -1]
movey = [1, 0, -1, 0]

for i in range(N):
    country.append(list(map(int, input().split())))

stack = []
def dfs(x,y):
    global total
    global stack
    total += country[x][y]
    visited[x][y] = 1
    stack.append([x,y])

    for i in range(4):
        mx = x + movex[i]
        my = y + movey[i]

        if 0 <= mx < N and 0 <= my < N and L <= abs(country[x][y] - country[mx][my]) <= R and visited[mx][my] == 0:
            dfs(mx,my)

cnt = 0

while True:
    flag = 0
    visited = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if visited[i][j] == 0:
                dfs(i,j)
                if total > country[i][j]:
                    flag = 1
                    leng = len(stack)
                    avg = total // leng
                    for x in stack:
                        xx, yy = x
                        country[xx][yy] = avg
                total = 0
                stack = []
    if flag == 1:
        cnt += 1
    else:
        break

print(cnt)