[백준 16234] 인구 이동- python (solved.ac - 골드 5)

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

16234번: 인구 이동

풀이

문제를 보았을 때 알 수 있는 힌트

문제에서 이야기하는 조건과 bfs만 알고 있으면 풀 수 있는 문제이다.

다만 시간을 줄이기 위해서는 여러가지 공부가 필요할듯하다.

 

문제 내용을 잘 보면 옆의 나라의 인구 차이가 L과 R 사이에 있다면 같이 공유한다고 한다. 이를 생각하여 연결된 모든 국경 인원을 저장하고 나라 수 만큼의 평균을 만들고 기존의 그래프에 저장 시키면 된다.

이를 2000번 반복 할수 있게 하고 변경 사항이 없다면 종료하면 끝이 난다.

 

import sys
from collections import deque
dx = [0,0,1,-1]
dy = [1,-1,0,0]
input = sys.stdin.readline

n,l,r = list(map(int,input().split()))
graph = [list(map(int,input().split())) for _ in range(n)]
result =0
def bfs(sum,count,visited,queue):
    # y,x = queue
    visited_list = deque([queue[0]])
    while queue:
        y,x = queue.popleft()
        for i in range(4):
            vy = y+dy[i]
            vx = x+dx[i]
            if -1<vy<n and -1<vx<n and visited[vy][vx]==False:
                if l<=abs(graph[vy][vx]-graph[y][x])<=r:
                    visited[vy][vx]=True
                    sum += graph[vy][vx]
                    queue.append([vy,vx])
                    visited_list.append([vy,vx])
                    count+=1
    # print(sum)
    
    # 가능한 경우를 다 찾음
    # 이제 변경해야함.
    if count > 1:
        changed_value = sum//count
        for y,x in visited_list:
                    graph[y][x] = changed_value
        return True
    else:
        return False

# 입력 완료

# dfs 구현하기
# print(graph)

# 2000일을 돌수 있게 해야함.
# 초기화 
for _ in range(2000):
    visited = [[False]*n for _ in range(n)]
    total_bool = False
    for i in range(n):
        for j in range(n):
            if visited[i][j] == False:
                visited[i][j]=True
                queue = deque()
                queue.append([i,j])
                change_bool = bfs(graph[i][j],1,visited,queue)
                if change_bool:
                    total_bool =True
    if total_bool:
        result +=1
    else:
        break
            
print(result)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/python/baekjoon16234_1.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리