16234_인구이동

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

16234번: 인구 이동

 

 

 

꽤나 헤맸었던 문제다..

 

처음에는 유니온파인드로 풀까 하다가 결국 같은 집합을 만들어도 그들의 합으로 또 해당그룹의 수를 바꾸려면 두번 일해야한다는걸 깨닫고 그냥 bfs를 사용해서 그때그때 집합을 만들어 구현하였다.

 

 

시간초과나 메모리초과때문에 엄청 고생했는데 bfs를 맵에서 검사할때 한바퀴돌때 이미 집합에 넣어서 검사할 필요가 없는부분은 bfs를 검사하면 안되었었고, 특히 bfs안에서 q에 넣을때 인접한 부분의 집합을 넣을때 q에 넣으면서 visited를 넣어야지 q에 중복되서 쌓이지 않기 때문에 메모리초과를 피할 수 있었다.

 

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

n,l,r = map(int,input().split())
city = [ list(map(int,input().split())) for _ in range(n)]


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

def bfs(i,j):
    q = deque()
    q.append((i,j))
    visited[i][j] = True
    union = [(i,j)]
    count = city[i][j]

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

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

            if 0<=nx<n and 0<=ny<n and visited[nx][ny] == 0 and l<=abs(city[nx][ny]-city[x][y])<=r:
                union.append((nx,ny))
                count += city[nx][ny]
                q.append((nx,ny))
                visited[nx][ny] = True

    if len(union) > 1:
        value = count // len(union)
        for x,y in union:
            city[x][y] = value


    return len(union)




cnt = 0
while True:
    flg = False
    visited = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                if bfs(i,j)>1:
                    flg = True
    if not flg:
        break
    # for q in city:
    #     print(q)
    # print('---------')
    cnt +=1
print(cnt)