[백준 16234번] 인구 이동

 

from collections import deque
import math
N, L ,R = map(int,input().split())

data = [list(map(int,input().split())) for _ in range(N)]

visited = [[False]*N for _ in range(N)]

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

count = 0

def bfs(x,y): # 국경선을 열고 인구를 이동시키는 BFS 함수
    if visited[x][y]: # 이미 방문한 곳이면 Pass
        return False

    visited[x][y] = True
    group = [(x,y)] # 연합을 이룬 좌표 목록
    total = data[x][y] # 연합의 총합

    queue = deque([(x,y)])

    while queue:
        temp_x, temp_y = queue.popleft()
        for i in range(4):
            nx = temp_x + dx[i]
            ny = temp_y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                if L <= abs(data[temp_x][temp_y]-data[nx][ny]) <= R:
                    queue.append((nx,ny))
                    visited[nx][ny] = True
                    group.append((nx,ny)) # 연합에 추가
                    total += data[nx][ny] # 연합의 총합에 더하기

    if len(group) > 1: # 연합을 이루었을 경우 인구수 조정한 후 True 반환
        average = math.trunc(total / len(group))
    
        for group_x,group_y in group:
            data[group_x][group_y] = average

        return True
    else: # 연합을 이루지 못하였을 경우 False 반환
        return False

def check(): # 인구 이동이 있었는지 확인하는 함수
    is_moved = False

    for i in range(N):
        for j in range(N):
            if bfs(i,j): # bfs 함수가 True를 반환하면 인구 이동이 있었다고 판단
                is_moved = True

    return is_moved

while 1:
    if not check(): # 인구 이동이 발생하지 않았다면 무한루프 탈출
        break
    else: # 인구 이동이 발생했다면 +1 카운팅
        count += 1
	
    visited = [[False]*N for _ in range(N)] # 새로운 인구 이동을 위해 방문여부 배열 초기화

print(count)

이번 문제는 인구 차이가 L 이상, R 이하일 때 국경선을 열도록 하고 인구 이동을 시킨다는 조건하에 총 인구가 이동한 횟수를 구하는 문제이다.

 

처음에는 복잡하게 로직을 고민했었는데 고민을 하다보니 DFS나 BFS를 사용하여 땅을 연결시켜준 뒤에, 인구 이동이 있었다면 True를 반환하고 인구 이동이 없었다면 False를 반환하는 방식을 떠올리게 되었다.

 

따라서 '국경선을 열고 땅을 연결시켜주는 함수(bfs)'와 '모든 땅을 순회하면서 인구 이동을 시켜주고 인구 이동이 발생했는지 판단해주는 함수(check)'를 구현하여 마침내 풀이할 수 있었다 :)

 

다만, 인구 이동을 시켜줄 때 마다 visited 함수를 초기화 시켜주지 않으면 원하는 결과가 나오지 않을 수 있기 때문에 꼭 초기화를 해주어야 한다(이 부분 때문에 잠깐 테스트케이스가 성공하지 않았었다 🥲) 🚨