[python] 백준 - 16234 (인구 이동)

2026.01.13ko 0 시리즈 · 알고리즘 #알고리즘

골드4 문제이며, 제한 시간은 2초이다.

문제

해결 과정

그냥 BFS를 이용하며 조건에 범위를 벗어나지 않고, 방문하지 않았고, 국경선을 열 수 있다면 BFS를 돌리며 해당 좌표와 합을 저장 후 그래프를 수정한다. 더 이상 연합이 없을 때까지 돌리는 방식으로 구현했다.

풀이

from collections import deque

def bfs(x, y):
  queue = deque()
  queue.append((x, y))
  cnt = 1
  sum = graph[x][y]
  visited[x][y] = True
  people = [(x, y)]

  while queue:
    x, y = queue.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]:
        if a <= abs(graph[x][y] - graph[nx][ny]) <= b:
          cnt += 1
          sum += graph[nx][ny]
          queue.append((nx, ny))
          visited[nx][ny] = True
          people.append((nx, ny))

  value = sum // cnt
  for i, j in people:
    graph[i][j] = value
  return cnt

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

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

answer = 0
while True:
  visited = [[False] * n for _ in range(n)]
  flag = False
  for i in range(n):
    for j in range(n):
      if not visited[i][j]:
        if bfs(i, j) > 1:
          flag = True
  if not flag:
    break
  answer += 1
print(answer)

bfs구현이 어렵진 않았다. 헷갈리는 부분은 무한루프의 종료조건이 헷갈렸었다. 하루가 끝나고 연합이 없으면 종료해야되는데 자꾸 연합이 없는 경우 바로 종료되어서 flag 설정에서 애를 좀 먹었다.

아직 댓글이 없습니다.

문제

해결 과정

풀이

댓글

댓글 쓰기