[BOJ] Q16234 인구 이동

[BOJ] Q16234 인구 이동

Question

Language: Python

Difficulty: Gold 5

국경선을 경계로 인구 수 차이가 L~R 인 두 나라는 경계선을 열고 서로 열고, 같은 연합에 속하게 된다.

우선, BFS을 통한 component을 찾아서 해당 component에 대해 개별적으로 인구 이동을 진행한다.

이 과정을 component 개수가 노드의 개수 만큼 될때까지 반복한다. (component=노드 ==> 더 이상 연합이 존재하지 않는 다는 의미이다.)

그래프에서 component 개수는 bfs을 실행한 총 회수인것이다.

Component Search

for i in range(1,n+1):
    for j in range(1,n+1):
        if not visited[i][j]:
            bfs(i,j)
            count+=1

여기서 count가 총 component 개수이다.

Solution

from math import pow
from collections import deque
def bfs(row,col):
    # component을 구해서 해당 component에 대한 인구 이동 작업을 처리한다.
    union=[(row,col)]
    visited[row][col]=True
    q=deque()
    q.append((row,col))
    sumOfCitizens=graph[row][col]
    count=1
    while q:
        row,col=q.popleft()
        
        for dir in range(4):
            new_row=row+dy[dir]
            new_col=col+dx[dir]

            if new_row < 0 or new_row >=n or new_col <0 or new_col>=n:
                continue

            if visited[new_row][new_col]:
                continue

            #인구 수 차이 L~R 사이면 component에 추가
            if L<=abs(graph[new_row][new_col]-graph[row][col])<=R:
                union.append((new_row,new_col))
                q.append((new_row,new_col))
                sumOfCitizens+=graph[new_row][new_col]
                count+=1
                visited[new_row][new_col]=True
                
    #인구 이동 진행
    for row,col in union:
        graph[row][col]= sumOfCitizens//count
    return union

if __name__ == "__main__":
    n,L,R=map(int,input().split())
    graph=[]
    for _ in range(n):
        graph.append(list(map(int,input().split())))

    answer=0  
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]
  
    while True:
        index=0
        visited=[[False]*n for _ in range(n)]      
        for row in range(n):
            for col in range(n):
                if visited[row][col]:
                    continue
                visited[row][col]=True
                bfs(row,col)
                index+=1
        if index== int(pow(n,2)):
            break
        answer+=1
print(answer)