[ 백준 16234 ] 인구 이동 - Python

문제 보기

 

이 문제는 bfs 문제이다. (+시간 초과 해결)

 

• 문제 접근
  1. 인구 차이를 통해서 국경선을 열고 닫으며, 몇 번의 인구 변화가 일어나는지 파악하는 문제이다.
  2. 국경선을 열 때마다 인구 변화를 일으키는 것이 아니라 전체 국경선 형태를 파악한 후 한 번에 값을 업데이트한다. (시간 초과 관련)
  3. 국경선을 열 수 없을 때까지 진행한다.
• 알고리즘
  1. 현재 위치에서 지나갈 수 있는 집합을 파악한다. (원소 위치, 원소 개수, 원소 합) - bfs
  2. 1번의 과정을 전 구간에 실시한다.
  3. 값을 업데이트하고 다시 1번으로 돌아간다. 만약 업데이트할 값이 없다면 종료한다.

 

코드

import sys
from _collections import deque

# 상, 하, 좌, 우
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]


def bfs(row, col):
    check = False
    visited = {(row, col)}
    q = deque([(row, col)])
    val, cnt = 0, 0

    while q:
        row, col = q.popleft()
        val += arr[row][col]
        cnt += 1
        for i in range(4):
            new_row, new_col = row + dy[i], col + dx[i]

            if 0 <= new_row < N and 0 <= new_col < N and (new_row, new_col) not in visited and L <= abs(arr[new_row][new_col] - arr[row][col]) <= R:
                q.append((new_row, new_col))
                visited.add((new_row, new_col))
                check = True
    return val // cnt, visited, check


def move():
    # 인구 이동
    cnt, pre_cnt = 0, 0
    while True:
        is_Move = False
        total_visited = set()
        temp = []
        for i in range(N):
            for j in range(N):
                if (i, j) not in total_visited:
                    value, visited, flag = bfs(i, j)
                    if flag:
                        is_Move = True
                    temp.append((value, visited))
                    total_visited |= visited

        for (value, visit) in temp:
            for y, x in visit:
                arr[y][x] = value
        if not is_Move:
            return cnt
        cnt += 1


if __name__ == "__main__":
    N, L, R = map(int, sys.stdin.readline().split())
    arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

    print(move())