Algorithms/백준

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

devran 2024. 2. 29. 15:12
반응형

🥇 인구 이동

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

💡 아이디어

  1. 인접한 나라의 국경선을 열지 말지 탐색을 이용해서 구한다
  2. 국경선을 열 경우, 연합 배열에 해당 좌표를 넣어준다
  3. 열어진 국경선의 총 합을 토대로 각 연합의 인구수 / 연합의 크기를 계산하여 연합 배열에 속한 각 칸의 인구수를 재설정 해준다.
  4. 인접한 나라 탐색이 끝날때 마다 날짜를 +1 해준다

📂 풀이

# 인구이동
from collections import deque
import sys
input = sys.stdin.readline

# 인구이동을 위해 인접한 나라를 탐색
def bfs(x,y,l,r):
    q = deque()
    q.append([x,y])
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    visited[x][y] = True
    union = [[x,y]] # 연합에 속한 나라 좌표
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx<n and 0<=ny<n and not visited[nx][ny]:
                # 인접한 나라와의 인구 수 차이가 l이상 r이하여야 함
                if l <= abs(graph[nx][ny] - graph[x][y]) <= r:
                    visited[nx][ny] = True
                    q.append([nx,ny])
                    union.append([nx,ny]) # 연합에 추가
    
    if len(union) > 1:
        # union안의 좌표를 바탕으로 인구수 모두 더해주기
        avg_pop = sum([graph[cx][cy] for cx,cy in union]) // len(union)
        for cx, cy in union: # 연합안의 모든 좌표를 평균 인구수로 바꿔준다
            graph[cx][cy] = avg_pop
        return union # 연합 반환
    else:
        return []
# 메인
n, l, r = map(int, input().split())
graph = []
visited = [[False] * n for _ in range(n)] # 방문체크 배열
team = 0 # 연합의 개수
tmp_sum = 0 # 인구수
day = 0 # 날짜

# 연합 배열
for i in range(n):
    graph.append(list(map(int, input().split())))

# 탐색 시작
while True: 
    visited = [[False] * n for _ in range(n)] # 방문체크 배열
    moved = False # 인구 이동 확인 
    
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                union = bfs(i,j,l,r)
                if union : # 연합이 있다면?
                    moved = True # 인구 이동됨

    if not moved: # 인구가 이동하지 않았다면
        break # 반복문 탈출
    
		# 인구가 이동할 경우 더이상 이동 못할때 까지 반복, day += 1
    day += 1

print(day)

⚠️ 느낀점

BFS 코드 짜는 것 보다 더 어려웠던 것은,,

인구 이동을 확인하는 변수와 연합 배열을 활용해서

한 번이라도 연합이 있었다면, 더 이상 이동이 불가할 때 까지 반복하고 날짜를 +1 해주고

연합이 없다면 break를 해주는 이 부분이 제일 어려웠다.

# 탐색 시작
while True: 
    visited = [[False] * n for _ in range(n)] # 방문체크 배열
    moved = False # 인구 이동 확인 
    
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                union = bfs(i,j,l,r)
                if union : # 연합이 있다면?
                    moved = True # 인구 이동됨

    if not moved: # 인구가 이동하지 않았다면
        break # 반복문 탈출
    
		# 인구가 이동할 경우 더이상 이동 못할때 까지 반복, day += 1
    day += 1

print(day)
반응형