백준 16234 - 파이썬

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

16234번: 인구 이동

문제 풀이

처음에 문제를 읽고 이해가 안 되었는데 그림 설명과 함께 보니 금방 이해가 됐다. BFS로 푸는 문제이며 그리디 문제이기에 문제에 나온 조건대로 코딩하면 금방 해결할 수 있다. (코딩하다가 막혀서 다른 사람 풀이 본건 안비밀)

 

코드

import sys
input = sys.stdin.readline
from collections import deque

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

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

def bfs(x,y):
  q = deque()
  temp = []
  q.append((x,y))
  temp.append((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]:
        if l <= abs(graph[nx][ny] - graph[x][y]) <= r:
          q.append((nx,ny))
          temp.append((nx,ny))
          visited[nx][ny] = True

  return temp

result = 0

while True:
  flag = 0
  visited = [[False] * (n +1) for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if not visited[i][j]:
        visited[i][j] = True
        country = bfs(i,j)
        if len(country) > 1:
          flag = 1
          number = sum(graph[x][y] for x,y in country) // len(country)
          for x,y in country:
            graph[x][y] = number

  if flag == 0:
    break

  result += 1

print(result)

위 코드는 해당 블로그를 참고하였다. bfs탐색하면서 국가간 인구 차이가 L명 이상 R명 이하인 경우 이동할 국가의 위치를  temp라는 변수에 저장하고, temp를 리턴하여 해당 리스트에 저장된 위치를 가지고 문제의 답을 출력하는 코드이다.

 

 느낀점

while문을 따로 빼서 국가간 연합하여 인구가 이동한 기간을 계산했는데, 이것을 BFS탐색 시 한번에 하려고 한게 문제였던거 같다. 복잡한 문제일수록 나눠서 보면 간단하다는 것을 다시 한번 더 느꼈다. 또한 BFS 문제는 문제에 주어진 조건대로 코딩하면 금방 답을 도출할 수 있기에 문제를 차근차근 이해하고 코드로 옮기는 것이 중요한거 같다.