16234번 - 인구 이동

문제

 

16234번: 인구 이동 (acmicpc.net)

16234번: 인구 이동

풀이 1

이전에 예제로 풀었던 "음료수 얼려먹기" 문제와 유사하다. 어떤 노드에 대해 인접 노드가 특정 조건을 만족하면 방문하는 DFS나 BFS를 이용해 풀면 된다. 소위 "음료수 채우기" 가 완료되면, 방문한 모든 노드의 값을 평균을 내어 다시 할당해야 하는 작업도 추가적으로 해줘야한다. 이 작업은 연합 형성이 불가능할 때까지 반복한다.

 대강의 설계가 끝났으니 구현에 들어갈 차례이다. 한 사이클에서 연합 형성, 즉 음료수 채우기를 먼저 해야하는데, 이 문제에서는 연합 별로 서로 다른 숫자를 배정한다. 또한 당연히 아직 방문하지 않은 노드에 대해서만 작업을 시행해야 한다는 점과 나중에 각 연합에 대해 인구와 회원국 수를 취합하여 인구 이동을 구현해야 한다는 점도 고려한다. 만약 DFS로 풀면, 재귀적으로 인구와 회원국 수 취합을 구현해야 한다는 점 때문에 해당 정보들은 다음과 같이 DFS 외부에 빼놓고 갱신해야 할 것이다. 또한 최대 재귀 한도 에러가 발생할 수 있으니, 한도를 높여주는 코드도 추가해줘야 한다.

def dfs(row,col):
  # 노드 방문처리 ...
  	# 노드에 연합명 (숫자) 배정
  	# teams[총 인구수][회원국 수] 갱신
  for i in range(4):
    nRow = row + dRow[i]
    nCol = col + dCol[i]
    if nRow >= 0 and nRow < n and nCol >= 0 and nCol < n:
      diff = abs(data[row][col] - data[nRow][nCol])
      # 인접 국가와의 인구수 차이 조건, 그리고 다음 노드가 아직 방문하지 않은 노드일 때
      if L <= diff <= R and allies[nRow][nCol] == -1:
        dfs(nRow,nCol)

while True:
  # 연합 해제
  allies = [[-1]*n for _ in range(n)]
  teamNum = 0
  teams = []
  # 연합 형성
  for row in range(n):
    for col in range(n):
      # 아직 방문하지 않은 노드, 즉 연합이 정해지지 않은 국가를 찾으면
      if allies[row][col] == -1:
        # teams[총 인구수][회원국 수] 초기화
        teams.append([0,0])
        dfs(row,col)
        teamNum += 1
  # 연합 형성 불가능 시, 즉 모든 국가가 서로 연합을 이룰 수 없을 때 프로그램 종료
  if teamNum == n*n:
    print(days)
    exit()
  # 인구 이동
  avg = list(map(lambda x : x[0] // x[1], teams))
  for row in range(n):
    for col in range(n):
      data[row][col] = avg[allies[row][col]]

 반면 BFS 로 구현할 경우 DFS처럼 인구 이동을 굳이 바깥에 빼지 않아도 된다. 

코드

DFS

import sys
sys.setrecursionlimit(100000)

input = sys.stdin.readline
n,L,R = map(int,input().split())
data = [list(map(int,input().split())) for _ in range(n)]

# 북, 동, 남, 서
dRow = [-1,0,1,0]
dCol = [0,1,0,-1]

days = 0

def dfs(row,col):
  allies[row][col] = teamNum
  teams[-1][0] += data[row][col]
  teams[-1][1] += 1
  for i in range(4):
    nRow = row + dRow[i]
    nCol = col + dCol[i]
    if nRow >= 0 and nRow < n and nCol >= 0 and nCol < n:
      diff = abs(data[row][col] - data[nRow][nCol])
      if L <= diff <= R and allies[nRow][nCol] == -1:
        dfs(nRow,nCol)

while True:
  # 연합 해제
  allies = [[-1]*n for _ in range(n)]
  teamNum = 0
  teams = []
  # 연합 형성
  for row in range(n):
    for col in range(n):
      if allies[row][col] == -1:
        # [sum, cnt]
        teams.append([0,0])
        dfs(row,col)
        teamNum += 1
  # 연합 형성 불가능 시 탈출
  if teamNum == n*n:
    print(days)
    exit()
  # 인구 이동
  avg = list(map(lambda x : x[0] // x[1], teams))
  for row in range(n):
    for col in range(n):
      data[row][col] = avg[allies[row][col]]

  days += 1

BFS

from collections import deque

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

dRow = [-1,0,1,0]
dCol = [0,-1,0,1]

result = 0

def bfs(row,col,team_num):
  allies = []
  allies.append((row,col))
  q = deque()
  q.append((row,col))
  union[row][col] = team_num
  population = graph[row][col]
  members = 1
  while q:
    row,col = q.popleft()
    for i in range(4):
      nRow = row + dRow[i]
      nCol = col + dCol[i]
      if 0 <= nRow < n and 0 <= nCol < n and union[nRow][nCol] == -1:
        diff = abs(graph[nRow][nCol] - graph[row][col])
        if l <= diff <= r:
          q.append((nRow,nCol))
          union[nRow][nCol] = team_num
          population += graph[nRow][nCol]
          members += 1
          allies.append((nRow,nCol))
  for row,col in allies:
    graph[row][col] = population // members

days = 0

while True:
  union = [[-1]*n for _ in range(n)]
  team_num = 0
  for row in range(n):
    for col in range(n):
      if union[row][col] == -1:
        bfs(row,col,team_num)
        team_num += 1
  if team_num == n*n:
    break
  days += 1

print(days)

풀이 2

보드를 순회하며 각 연합의 총 인구수와 해당 연합에 속할 칸의 수를 구한 뒤, 다시 보드를 순회하며 인구를 갱신하면 되는 간단한 문제이다. 만약 연합의 개수가 N*N개가 된다면 더이상 인구이동이 일어날 일이 없다는 뜻이되므로, 이를 기준으로 반복문을 종료한다.

from collections import deque

# 북 서 남 동
dRow = [-1,0,1,0]
dCol = [0,-1,0,1]

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

answer = 0
while True:
    # 연합 탐색
    visited = [[0]*N for _ in range(N)]
    states = [[-1]*N for _ in range(N)]
    team = 0
    unions = []
    for row in range(N):
        for col in range(N):
            if visited[row][col] == 0:
                states[row][col] = team
                # 총 인구수, 소속 국가 수
                union = [board[row][col],1]
                visited[row][col] = 1
                q = deque()
                q.append((row,col))
                while q:
                    r,c = q.popleft()
                    for i in range(4):
                        nr,nc = r+dRow[i],c+dCol[i]
                        if 0 <= nr < N and 0 <= nc < N and visited[nr][nc] == 0\
                        and L <= abs(board[r][c]-board[nr][nc]) <= R:
                            states[nr][nc] = team
                            union[0],union[1] = union[0]+board[nr][nc],union[1]+1
                            visited[nr][nc] = 1
                            q.append((nr,nc))
                unions.append(union)
                team += 1
    # 연합이 N*N개이면 종료
    if len(unions) == N**2:
        print(answer)
        break
    # 인구 이동
    unions = list(map(lambda x : x[0]//x[1],unions))
    for row in range(N):
        for col in range(N):
            board[row][col] = unions[states[row][col]]

    answer += 1