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

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

16234번: 인구 이동

 

이 문제는 너비 우선 탐색(bfs) 문제입니다.

배열 안의 각 칸은 나라를 의미하며, 조건에 맞을 시 주변 국가와 국경을 개방하여 인구를 이동시킵니다.

인구 이동은 매일 진행되며, 이 문제의 목표는 인구 이동이 며칠 동안 발생하는지 구하는 것이다.

 

접근 방식

1. 날마다 연합국 정보를 초기화한다.(어떠한 연합국에든 속하는지/속하지 않는지 판단하는 정보를 저장)

2. 각 국가를 순회하며(이중 for 문), 현재 국가가 어떠한 연합국에도 속하지 않으면 그 국가를 기준으로 너비 우선 탐색을 진행한다.

3. 너비 우선 탐색으로 연합국을 구한 후, 연합국의 인구를 계산한다.

4. 오늘 인구 이동이 한번이라도 일어났는지 판단한 후 그렇지 않다면 반복문을 종료한다.

 

전체 코드

제출 언어: PyPy3

시간: 1672ms

 

import sys
from collections import deque

def bfs(sr, sc):
    global mat, N, L, R, visited, dy, dx
    
    res = False
    queue = deque([(sr, sc)])
    visited[sr][sc] = True
    
    alliance_list = [(sr, sc)]

    while queue:
        cr, cc = queue.popleft()

        for i in range(4):
            nr, nc = cr + dy[i], cc + dx[i]

            if 0 <= nr < N and 0 <= nc < N and not visited[nr][nc]:
                if L <= abs(mat[cr][cc] - mat[nr][nc]) <= R:
                    visited[nr][nc] = True
                    queue.append((nr, nc))
                    alliance_list.append((nr, nc))

    return alliance_list
    
if __name__ == "__main__":
    N, L, R = map(int, sys.stdin.readline().strip().split())

    mat = [ list(map(int, sys.stdin.readline().strip().split())) for _ in range(N) ]
    dy, dx = (-1, 0, 1, 0), (0, 1, 0, -1)
    answer = 0
    is_moved = True

    while is_moved:
        is_moved = False
        visited = [ [False] * N for _ in range(N) ]

        for i in range(N):
            for j in range(N):
                if not visited[i][j]:
                    alliance_list = bfs(i, j)

                    if len(alliance_list) > 1:
                        is_moved = True

                        alliance_pop = sum([ mat[ar][ac] for ar, ac in alliance_list ]) // len(alliance_list)

                        for ar, ac in alliance_list:
                            mat[ar][ac] = alliance_pop

        if is_moved:
            answer += 1
        
    print(answer)

---

읽어 주셔서 감사합니다 :)

틀린 부분이 있다면 댓글로 편히 알려주세요😊