[백준] 16234. 인구 이동 (Python)

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

16234번: 인구 이동

 

✏️ 국경을 서로 공유하는 국가를 어떻게 처리해야 할지 고민하다가 리스트에 따로 담아주었다 (deque에서는 pop을 하니까)

✏️ union(국경 공유 국가 담아주는 곳)을 처음엔 set으로 했는데, 80% 쯤에서 시간 초과가 나서 list로 바꿔주었다.

✏️ 딴에는 중복 방지하겠다고 set을 쓴 거였는데, 생각해보니 set을 쓰지 않아도 중복값이 들어갈 일이 없었다.

 

from collections import deque

def BFS(y, x):
    q = deque()
    q.append((y, x))
    union = set()
    union.add((y, x))
    while q:
        ny, nx = q.popleft()
        dir = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for i, j in dir:
            dy, dx = ny+i, nx+j
            if 0 <= dy < N and 0 <= dx < N and visit[dy][dx] != 1:
                if L <= abs(board[ny][nx] - board[dy][dx]) <= R: # 인구수 차이가 조건에 맞으면
                    visit[dy][dx] = 1 # 방문 체크
                    q.append((dy, dx)) # q에 담아주기
                    if (dy, dx) not in union:
                        union.add((dy, dx)) # union set에 담아주기 (국경 공유)
    return union

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

board = [list(map(int, input().split())) for _ in range(N)]
ans = 0

while True:
    visit = [[0]*N for _ in range(N)]
    flag = False
    for y in range(N):
        for x in range(N):
            if visit[y][x] != 1:
                visit[y][x] = 1
                nation = BFS(y, x) # 한 번도 들린 적 없으면 BFS 돌리기
                if len(nation) > 1: # 국경선 열었다는 뜻 (1이면 국가 1개이므로 연산할 필요 X)
                    flag = True # flag 바꾸기
                    res = 0
                    for i, j in nation: # 국경선 공유하고 있는 국가들 인구 수 다 더하고
                        res += board[i][j]
                    res //= len(nation) # 공유하고 있는 국가 수로 나누기
                    for i, j in nation:
                        board[i][j] = res # 인구수 재분배
    if flag == False: # 국경선 연 적 한 번도 없으면
        break # 브레이크

    ans += 1 # +1일

print(ans)