[구현] 백준 16234 : 인구이동 - 파이썬 Python

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

16234번: 인구 이동

 

생각하기

문제에서 제시된 기준을 기반으로 인구가 각 날에 이동할 수 있는 블락들을 bfs를 이용하여 묶어본다

묶을 수 있다면 계속 이동해도 된다는 얘기 -> 묶지 못할 때까지 계속 day를 증가시켜가면서 이동해보자

 

시간복잡도

모든 칸에 대해서 조사 : O(N^2)

최대 인구 이동 가능 : 2000 

2000 x ( N^2 )

구현하기

• united - bfs를 돌면서 묶을 수 있는 박스들을 '연합'이라는 리스트에 담아둔 후에 추후 다시 united 리스트 안에 있는 좌표들을 대상으로 인구를 재정비 한다
• visited - 방문 체크 array는 각 날이 바뀔 때 마다 다시 초기화해분다
• people_sum - 묶을 수 있는 박스들을 방문할 때 마다 더해준다 -> 추후 한번더 united를 돌지 않게 하기 위함

from collections import deque

N, L, R = map(int, input().split())

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

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

day = 0
while True:

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

    for r in range(N):
        for c in range(N):
            if visited[r][c] == True:
                continue
            q = deque()
            q.append((r,c))
            united = [(r, c)]
            people_sum = A[r][c]
            visited[r][c] = True

            while q:
                y, x = q.popleft()

                for i in range(4):
                    ny = y + dy[i]
                    nx = x + dx[i]

                    if 0<= ny < N and 0 <= nx < N and visited[ny][nx] == False:
                        if L<= abs(A[ny][nx] - A[y][x]) <= R:
                            q.append((ny, nx))
                            united.append((ny, nx))
                            people_sum += A[ny][nx]
                            visited[ny][nx] = True


            if len(united) == 1:
                continue
            else:
                move = True
                after_cnt = people_sum//len(united)
                for n in united:
                    A[n[0]][n[1]] = after_cnt
            
    if move is True:
        day+=1
    else:
        break

print(day)

 

 

참고로 dfs로도 풀이가 가능하다 

 

python으로 푼다면 boj 서버에서는 recursion limit이 1000으로 설정되어있으므로 

문제에서 최대 2000번 보다 작은 인구이동이 발생하는 테케만 있다고 하였으니

setrecursionlimit을 적절히 3000정도로 하였다

 

import sys
sys.setrecursionlimit(3000)

N, L, R = map(int, input().split())

A = []

for _ in range(N):
    A.append(list(map(int, input().split())))

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

def dfs(row, col, united):
    global pop_sum, visited

    visited[row][col] = True
    united.append((row, col))
    pop_sum += A[row][col]
    for d in range(4):
        ny = row + dy[d]
        nx = col + dx[d]
        if 0<= ny < N and 0<= nx <N:
            if (L <= abs(A[row][col] - A[ny][nx]) <= R) and visited[ny][nx] is False:
                united = dfs(ny, nx, united)
    
    return united


day = 0
while True:
    visited = [[False] * N for _ in range(N)]
    day_continue = False
    for i in range(N):
        for j in range(N):
            if visited[i][j] == False:
                united = []
                pop_sum = 0
                united = dfs(i, j, united)
                united_len = len(united)
                if united_len != 1:
                    day_continue = True
                    for c in united:
                        A[c[0]][c[1]] = pop_sum // united_len
    
    if day_continue is False:
        break
    else:
        day+=1

print(day)