[백준/파이썬] 16234번 인구 이동

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

 

bfs를 여러번 돌려서 구역을 찾는 문제다

이렇게 반복을 많이 해도 되나..? 싶은 문제들은 보통 입력의 크기가 20,50,100 이정도 수준이므로 걱정하지 않아도 된다.

다만 좀 까다로운 점은 구역을 나중에 계산해줄 때이다

 

그냥 배열 하나 더 만들어서 연합(구역)별 값을 따로 저장해주고, country 리스트를 한번 더 돌면서 값을 일일이 넣어주었다.

 

더 좋은 방법 있으면 댓글로 공유 부탁드려요!

from collections import deque

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

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

def bfs(block,x,y):
    corp,cnt = 0,0
    dq = deque()
    dq.append((x,y))
    cnt += 1
    corp += country[x][y]
    
    while dq:
        sx, sy = dq.popleft()
        visited[sx][sy]=block

        for d in range(4):
            nx = sx + dx[d]
            ny = sy + dy[d]

            if nx >= 0 and ny >=0 and nx < N and ny < N and visited[nx][ny]==0:
                if L <= abs(country[nx][ny] - country[sx][sy]) <= R:
                    visited[nx][ny]=block
                    dq.append((nx,ny))
                    cnt += 1
                    corp += country[nx][ny]
    #print(corp,cnt)
    return corp//cnt
day = 0
while True:
    block = 1
    arr = [0]
    visited =[[0]*N for _ in range(N)]
    
    for i in range(N):
        for j in range(N):
            if visited[i][j]==0:
                new_value = bfs(block,i,j)
                arr.append(new_value)
                block+=1
    #print(country)
    if block == (N*N)+1 : break
    day+=1
    for i in range(N):
        for j in range(N):
            num = visited[i][j]
            country[i][j] = arr[num]
print(day)