파이썬) 인구이동 -BOJ

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

16234번: 인구 이동

 

 

 

이 문제를 읽었을 때 좀 쉬워보였다.

그러나 머지않아 문제를 발견했다.

bfs를 통해 얻은 값들 중 최초 visit[i][j] == False인 i,j값을 어떻게 할까, 또 visit[i][j] == False지만 주변국가들이 모두 만족하지 않았을 때였다.

그러나 고민은 곧 해결되었다.

애초에 contries 배열에 i,j를 append시키고 만약 contries의 길이가 1이라면 returnValue에 append시키지 않는다.

그럼 while문이 bfs로부터 얻은 값의 길이가 0일때 탈출하는 탈출조건을 만들 수가 있었다.

그 외에는 간단하다.

bfs로부터 얻은 값들의 길이와 avg를 구하고 arr의 값들을 업데이트한다.

from collections import deque
from copy import deepcopy

n, l, r = map(int, input().split())

arr = []

for i in range(n):
    arr.append(list(map(int, input().split())))

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


def bfs():
    ar = deepcopy(arr)
    visit = [[False for _ in range(n)]for _ in range(n)]
    returnValue = []
    for i in range(n):
        for j in range(n):
            if visit[i][j] == False:
                q = deque()
                visit[i][j] = True
                q.append((i, j))
                contries = [[i, j]]
                while q:
                    x, y = q.popleft()

                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]

                        if 0 <= nx < n and 0 <= ny < n:
                            if visit[nx][ny] == False:
                                if l <= abs(ar[x][y] - ar[nx][ny]) <= r:
                                    q.append((nx, ny))
                                    visit[nx][ny] = True
                                    contries.append([nx, ny])
                if (len(contries) != 1):
                    returnValue.append(contries)

    # returnValue = [value for value in returnValue if len(value) != 1]
    return returnValue


answer = 0

while True:

    contry_arr = bfs()

    if not contry_arr:
        # print(contry_arr)
        break

    else:
        for i in contry_arr:
            s = 0
            for j in range(len(i)):

                s += arr[i[j][0]][i[j][1]]
            avg = s // len(i)
            for j in range(len(i)):
                arr[i[j][0]][i[j][1]] = avg
        answer += 1

print(answer)