인구 이동

from collections import deque, defaultdict


def bfs(q):
    cnt, tmp = 1, []

    while q:
        item = q.popleft()
        row, col = item[0], item[1]
        visited[row][col] = True
        tmp.append([row, col])

        for xx, yy in zip(dx, dy):
            nx, ny = row + xx, col + yy
            if 0 <= nx < N and 0 <= ny < N:
                if not visited[nx][ny] and (L <= abs(maps[row][col] - maps[nx][ny]) <= R):
                    q.append([nx, ny])
                    visited[nx][ny] = True
                    cnt += 1

    temp[cnt].append(tmp)


def update():
    for cnt, values in temp.items():
        for item in values:
            addSum = 0
            for row, col in item:
                addSum += maps[row][col]
            pop = addSum // cnt
            for row, col in item:
                maps[row][col] = pop


def checkMoves():
    for i in range(len(maps)):
        for j in range(len(maps)):
            curr = maps[i][j]
            for xx, yy in zip(dx, dy):
                nx, ny = i + xx, j + yy
                if 0 <= nx < N and 0 <= ny < N:
                    if L <= abs(maps[nx][ny] - curr) <= R:
                        return True
    return False


N, L, R = map(int, input().split())
maps = [[] for i in range(N)]
visited = [[False for i in range(N)] for j in range(N)]
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

for i in range(N):
    items = list(map(int, input().split()))
    maps[i] = items

# BFS
q = deque()
move = 0

while True:
    if not checkMoves():
        break

    temp = defaultdict(list)
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                q.append([i, j])
                bfs(q)
    update()
    move += 1
    visited = [[False for i in range(N)] for j in range(N)]

print(move)

역시 삼성 기출답게 복잡한 구현 문제였다.

문제 상황 자체는 BFS만 잘 사용하면 돼서 그렇게 까다롭진 않았는데, 아무래도 이런 류의 문제가 익숙하지 않다보니 시간이 엄청 걸렸던 것 같다.(거의 2시간 가까이?)

그리고 각각의 함수에서 global을 선언하지 않아도 변수가 참조될 수 있다는 사실을 알았다. 전에는 함수 내에서는 무조건 global로 선언된 변수만 사용될 수 있는 줄 알았다.

ChatGPT의 설명

In your code, you don't need to declare visited as global because you are not reassigning it to a new object, but rather modifying its elements in place.

If you were to reassign visited to a new object inside the function, then you would need to declare it as global.

문제 출처: https://www.acmicpc.net/problem/16234