16234번 인구이동

문제

은근히 고려할 게 많아서 까다로웠던 문제였지만 재밌었다👀✨

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

접근 방식

dfs 재귀호출로 합을 누적시키기 위해 total을 전역 변수로 두고, 인구이동이 일어나는지 확인 용으로 flag 변수 역시 전역 변수로 뒀다. 각 위치를 기록하기 위해 pos_lst 리스트 변수를 두고 dfs를 돌며 추가하는 식으로 구현했다. 초기 dfs + 인접한 칸으로 이동할 수 있을 때 dfs가 호출되는데, 한번 호출될 때 방문 기록 뿐 아니라 total과 pos_lst가 갱신되도록 했다. 인접한 칸으로 이동할 수 있으면 flag를 True로 변환했다. 만약 전체 영역에 걸쳐 인구이동이 일어나지 않는다면 flag는 그대로 False로 남을 것이므로, 이럴 경우 while문을 break하여 끝낸다.

코드

import sys
sys.setrecursionlimit(10**6) #재귀호출 제한 늘리기

total = 0
flag = False #인구이동 일어나는지 check

def dfs(x, y, n, lands, l, r, visited, pos_lst):
    visited[x][y] = True
    pos_lst.append([x, y])
    global total
    total += lands[x][y]
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    for dx, dy in dirs:
        if 0 <= x + dx < n and 0 <= y + dy < n and not visited[x+dx][y+dy]:
            if l <= abs(lands[x+dx][y+dy] - lands[x][y]) <= r:
                global flag
                flag = True #인구이동이 일어나는 경우
                dfs(x + dx, y + dy, n, lands, l, r, visited, pos_lst)

def solution(n, l, r, lands):
    days = 0
    while True:
        global flag 
        flag = False
        visited = [[False] * n for _ in range(n)]
        pos_lst = []
        for i in range(n):
            for j in range(n):
                if not visited[i][j]:
                    global total
                    dfs(i, j, n, lands, l, r, visited, pos_lst)
                    if flag: #인구 이동이 가능한 경우
                        v = total // len(pos_lst)
                        for x, y in pos_lst:
                            lands[x][y] = v
                    pos_lst = [] #다시 초기화
                    total = 0
        if not flag: break
        days += 1
    return days

n, l, r = map(int, input().split())
lands = [list(map(int, input().split())) for _ in range(n)]
print(solution(n, l, r, lands))