[백준 16234번] 인구 이동 - Python으로 구현하기

[백준 16234번] 인구 이동 - Python으로 구현하기

 

문제 접근

• BFS로 주어진 조건과 연결된 노드들을 숫자로 표시해주자
• 노드들을 연결하면서 합과 개수를 구해 딕셔너리에 보관하자
• 행렬을 돌면서 자신의 union에 맞는 합과, 개수를 나누어 갱신해주자

 

생각해볼 점

• 종료조건이 괜찮은지?

 

오답 분석

• 연합개수*N*N 으로 구하지 않도록 주의, 메모리를 사용하자!

 

from collections import deque

def find_union(start,num):
    dq = deque()
    dq.append(start)
    union[start[0]][start[1]]=num
    union_sum=A[start[0]][start[1]]
    union_cnt=1
    while dq:
        x,y=dq.popleft()
        for k in range(4):
            nx=x+di[k][0]
            ny=y+di[k][1]

            if 0<=nx<N and 0<=ny<N and union[nx][ny]==-1 and L<=abs(A[x][y]-A[nx][ny])<=R:
                union_sum+=A[nx][ny]
                union[nx][ny]=num
                union_cnt+=1
                dq.append([nx,ny])
    return [union_sum,union_cnt]

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

di = [[-1,0],[0,-1],[1,0],[0,1]]
cnt=0
while True:
    union = [[-1] * N for _ in range(N)]
    n=0
    union_info={}
    for i in range(N):
        for j in range(N):
            if union[i][j]==-1:
                union_info[n]=find_union([i,j],n)
                n+=1

    if n==N*N:    # 모든 국경선이 열리지 않음
        break

    # 국경 업데이트
    for i in range(N):
        for j in range(N):
            A[i][j]=union_info[union[i][j]][0]//union_info[union[i][j]][1]
    cnt+=1
print(cnt)

 

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!