문제 링크 : https://www.acmicpc.net/problem/16234
난이도 : 골드 4
문제 유형 : 그래프, 너비 우선 탐색

문제 파악

• 이동은 하루 동안 아래 방법으로 인구 이동이 없을 때까지 지속
  • 국경선 공유 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
  • 위의 조건에 맞는 국경선이 모두 열렸다면, 인구 이동 시작
  • 국경선이 열려 있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
  • 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수) 가 된다.
  • 연합을 해체하고 모든 국경선을 닫는다.
• 입력
  • N : 나라의 수
  • L, R : 인구 차이의 범위
  • A[r][c] : 각 나라의 인구 수
• 출력
  • 인구 이동이 발생 하는 일 수

접근 방법

• BFS를 사용하여 연합을 형성할 수 있는 모든 나라를 탐색한다.
  • 연합의 조건 : 두 나라의 인구 차이가 L 이상 R 이하인 경우
  • 연합을 구성할 때는 방문 여부를 체크
  • 연합을 구성하는 각 나라들의 좌표와 인구수 추적 → 평균 값 구하기
  • 연합을 다 찾은 후에는 인구 수의 평균 값으로 인구 수 조정
• 인구 이동이 일어날 때마다 일 수 증가
• 인구 이동이 없을 때까지 반복해야 하므로 인구 이동을 했는지 확인이 필요하다.

코드 구현

import sys
input = sys.stdin.readline
from collections import deque

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

answer = 0

def bfs(si, sj):

    q = deque()
    q.append((si, sj))
    visited[si][sj] = 1
    union = [(si, sj)]
    total = arr[si][sj]

    while q:
        y, x = q.popleft()
        for iy, ix in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            dy = y + iy
            dx = x + ix
            if 0 <= dy < N and 0 <= dx < N:
                if visited[dy][dx] == 0:
                    if L <= abs(arr[y][x] - arr[dy][dx]) <= R:  # 연합 조건에 맞는 경우
                        q.append((dy, dx))  # 큐에 위치 추가
                        visited[dy][dx] = 1  # 방문 표시
                        union.append((dy, dx))  # 연합에 추가
                        total += arr[dy][dx]  # 총 인구수 합산

    if len(union) > 1:  # 연합인 경우
        avg = total // len(union)  # 연합의 새로운 인구 평균 계산
        for y, x in union:  # 인구 이동
            arr[y][x] = avg
        return 1  # 연합 발생하면 1 리턴 
    return 0  # 연합 없었던 경우 0 리턴

while True:
    visited = [[0]*N for _ in range(N)]
    flag = 0  # 인구 이동 확인 플래그
    for i in range(N):
        for j in range(N):
            if visited[i][j] == 0:  # 미방문한 곳 연합 확인
                flag = max(flag, bfs(i, j))

    if flag == 0:  # 인구 이동이 없었으면 종료
        break
    answer += 1

print(answer)