백준 #16234 인구이동

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline
from collections import deque

def solve(i, j):
    q = deque()
    q.append((i, j))
    union = []
    total = 0
    while q:
        r, c = q.popleft()
        union.append((r, c))
        total += arr[r][c]
        for k in range(4):
            nr = r + dr[k]
            nc = c + dc[k]
            if 0 <= nr < N and 0 <= nc < N and not visited[nr][nc]:
                if L <= abs(arr[nr][nc] - arr[r][c]) <= R:
                    q.append((nr, nc))
                    visited[nr][nc] = True

    avg = total // len(union)
    for r, c in union:
        arr[r][c] = avg
    return len(union)


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

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
cnt = 0

while True:
    check = False
    visited=[[False] * N for _ in range(N)]
    for r in range(N):
        for c in range(N):
            if not visited[r][c]:
                visited[r][c] = True
                if solve(r, c) > 1:
                    check = True
    if not check:
        break
    else:
        cnt += 1

print(cnt)

풀이

bfs 함수를 여러번 호출해야하는 문제였다. 인구 이동이 완전이 멈출 때까지 탐색 후 더이상 이동이 불가능할 경우 종료한다. 오늘도 역시 오전 8시부터 알고리즘 문제풀이를 진행했다!! 평소같았으면 긴장감 없이 문제를 풀기때문에 문제에 대한 집중도가 떨어졌을텐데 다같이 시간제한을 두고 푸니깐 몰입도가 확 올라가서 정말 좋은 것 같다. 내일도 화이팅이당!!