[백준 16234] 인구 이동 (파이썬)

문제

 

 

정답

 

bfs로 구현해야겠다. 그리고 구현은 했지만, 총 인구 이동을 구해야 했다.

그래서 인구 이동을 하고 난 후의 변한 상황을 다시 graph에 반영하고 반복문을 돌려야 했는데, 그게 잘 구현이 안됐다

 

먼저 인구이동 되는 x,y좌표를 넣어주기 위해서 united라는 배열을 생성했다

그리고 bfs에서 return값으로 넣주었다.

 

결국 while 문으로 연합된 나라가 있는 경우 flag=1로 설정해서 답을 구해준다.

county라고 받고 county가 있는 경우 값을 바꾸어준다 의외로 구현은 납득 가능한 수준의 문제였다:(

 

#bfs로 상하좌우 다 파악을 해서 count를 해준다
#sum도 구한다
#방문하지 않거나 연합인 국가가 아니면 반복해서 파악한다

from collections import deque

n,l,r=map(int, input().split())
graph=[]
for i in range(n):
    graph.append(list(map(int, input().split())))


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

#연합 국가 파악하고 sum이랑 count 구해줌
def bfs(x,y):
    united=[] #연합인 국가를 담는 리스트
    que=deque()
    que.append((x,y))
    united.append((x,y))

    while que:
        x,y=que.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<n and ny>=0 and ny<n:
                if l<=abs(graph[x][y]-graph[nx][ny])<=r:
                    if visited[nx][ny]==0:
                        visited[nx][ny]=1
                        que.append((nx, ny))
                        united.append((nx,ny))
    return united

res = 0
while True:
    visited=[[0]*(n) for _ in range(n)] #방문했는지 안했는지 파악
    flag=0

    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0:  # 방문하지 않은 국가에 대해서만 BFS 호출
                visited[i][j]=1
                country=bfs(i, j)  # 연합을 이루는 국가가 있을 경우

                if len(country)>1:
                    flag=1
                    total=sum(graph[x][y] for x,y in country)//len(country)
                    
                    for x,y in country:
                        graph[x][y]=total
    if flag==0:
        print(res)
        break
    res+=1