[백준] 16234_인구 이동 (bfs 이용)

📕 문제

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

16234번: 인구 이동

 

💡 풀이법

1. bfs를 이용해서 사방을 탐색하며 인덱스를 넘어가지 않고 인구 차이가 L이상 R이하이면 이동하면서 연합국가를 country라는 리스트에 담아준다.

2. bfs가 끝났을 때 country 리스트가 1이면 연합 국가가 없다는 뜻이기 때문에 country의 길이가 1 이상일 때만 평균 인구를 구해주고 avg_list에 담는다. country리스트도 country_list안에 담는다.

(이때, 바로 인구를 변화 시켜주면 이중 for문 안이기 때문에 시간이 오래 걸린다. 그래서 연합 국가들의 리스트를 country_list라는 리스트에 다 담아주고 나중에 한꺼번에 인구를 변화 시켜주는게 시간을 단축할 수 있다.)

3. 모든 for문을 다 돈 후에 avg_list가 있다면 move라는 함수를 통해서 한꺼번에 인구를 변화 시켜준다.

4. avg_list가 없다면 더이상 인구를 옮겨줄 필요가 없기 때문에 while문을 멈춘다.

5. while문의 마지막에 day += 1을 해주면서 날짜를 하루씩 추가해준다.

 

from collections import deque

def move(lst, avg_list):
    for countrys, avg in zip(lst, avg_list):
        for country in countrys:
            r, c = country
            matrix[r][c] = avg

dxy = [(1,0),(0,1),(-1,0),(0,-1)]
def bfs(x, y):
    global total
    deq = deque()
    deq.append((x,y))
    country.append((x, y))
    visited[x][y] = 1

    while deq:
        x, y = deq.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy

            if -1 < nx < N and -1 < ny < N and visited[nx][ny] == 0:
                if L <= abs(matrix[x][y] - matrix[nx][ny]) <= R:
                    deq.append((nx, ny))
                    total += matrix[nx][ny]
                    visited[nx][ny] = 1
                    country.append((nx, ny))

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

day = 0
while True:
    visited = [[0 for _ in range(N)] for _ in range(N)]
    country_list = []
    avg_list = []
    for i in range(N):
        for j in range(N):
            if visited[i][j] == 0:
                country = []
                total = matrix[i][j]
                bfs(i,j)
                cnt = len(country)
                if cnt > 1:
                    avg = total//cnt
                    avg_list.append(avg)
                    country_list.append(country)
                
    if avg_list:
        move(country_list, avg_list)
    else:
        break
    day += 1
print(day)

-> 끄응,, 절대 파이썬으로는 시간초과를 벗어날 수 없어서 pypy로 제출했더니 통과했다.. 뭔가 찝찝하지만 넘어갈래..ㅎ