[알고리즘/BFS] 16234번 : 인구 이동 - python

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

16234번: 인구 이동

 

---

• 문제
• 소요시간: 1시간 9분

---

• 설계하기(접근방법) 

1. 입력받기

나라의 인구를 입력받는다

 

2. 구현하기

조건에 맞는 나라를 기준으로

bfs를 통해서 하나의 연합 리스트를 구한다

 

모든 연합 리스트를 구했다면

각 연합에 대해서

총 인구/ 연합된 나라의 수 로

graph를 초기화 해준다.

 

한번이 이동이 끝난 후 다음 이동을 진행한다

 

3. 출력하기

총 이동 횟수를 출력한다

---

• 코드(출력)

from collections import deque

n , small ,big = map(int, input().split())

graph = [list(map(int,input().split())) for _ in range(n)]


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

def check_near(x,y):
    union = []
    q = deque()
    first = [x,y]
    q.append([x,y])
    while q:
        x,y = q.popleft()
        here = graph[x][y]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0 <= ny < n:
                if visited[nx][ny] == 0:
                    there = graph[nx][ny]
                    diff = abs(here - there)
                    if small <= diff <= big:
                        visited[nx][ny] = 1
                        union.append([nx,ny])
                        q.append([nx,ny])
    return union

trial = 0

while True:
    visited = [[0 for _ in range(n)] for _ in range(n)]
    union_list = []
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0:
                lst = check_near(i,j)
                if len(lst) != 0:
                    union_list.append(lst)
    if len(union_list) == 0:
        break
    trial += 1
    while union_list:
        unioned = union_list.pop()
        union_total = 0
        union_cnt = 0
        for i in unioned:
            x, y = i
            union_total += graph[x][y]
        new_union = union_total // len(unioned)
        for i in unioned:
            x,y = i
            graph[x][y] = new_union

print(trial)

---

• 얻어갈 부분

1. 문제의 조건을 잘못 이해해 시간이 좀 더 걸렸다. 연합은 연합끼리 새로 인구를 구해야 하는데, 모든 연합을 한 연합으로 묶어버려서 결과가 잘못 나왔다. 지문을 읽는데 시간을 좀 더 쓰자