[백준] 16234 인구이동

문제

• NxN 크기의 땅에 나라가 하나씩 존재하고, 살고 있는 인구가 칸마다 다르다.
• 인접한 나라 사이에 인구 이동이 없을 때까지 다음의 방식으로 인구 이동이 진행된다.
  • 1) 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면 두 나라가 공유하는 국경선을 오픈한다,
  • 2) 위 조건에 의해 열어야 하는 국경선이 모두 열리면 인구 이동을 시작한다.
  • 3) 국경선이 열려 있는 인접한 칸은 '연합'을 이루게 되고, 연합을 이루는 각 칸의 인구수는 (연합의 인구 수) / (연합을 이루는 칸의 개수) 가 된다. (편의상 소수점은 버린다.)
  • 4) 연합을 해체하고 모든 국경선을 닫는다.
•  각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하기
• 1 <= N <= 50
  1 <= L <= R <= 100

 

풀이 1

• 1) bfs를 통해 서로 연합이 될 수 있는 국가를 확인하고
• 2) 연합이 하나라도 존재하면 (인구 이동이 존재하면)
  • 2-1) 인구를 이동시키고
  • 2-2) 존재하지 않으면 인구 이동이 발생한 날을 출력한다.

 

from collections import deque

# 연합 확인하기
def check_union(x, y, graph, visited) :
    q = deque([(x, y)])
    union = [(x, y)]
    visited.add((x, y))

    while q :
        x, y = q.popleft()

        for i in range(4) :
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < N and 0 <= ny < N and (nx, ny) not in visited :
                if L <= abs(graph[x][y] - graph[nx][ny]) <= R :
                    visited.add((nx, ny))
                    q.append((nx, ny))
                    union.append((nx, ny))
    return union

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

dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)

day = 0
while True :
    # 국경선 열고 연합 확인
    unions = []
    visited = set()
    for x in range(N) :
        for y in range(N) :
            if (x, y) not in visited :
                union = check_union(x, y, graph, visited)
                if len(union) > 1 :
                    unions.append(union)
    
    # 인구 이동이 존재하는지 확인
    if not unions :
        break

    # 인구 이동 -> (연합의 인구 수) / (연합을 이루는 칸의 개수)
    for union in unions :
        p = sum([graph[i][j] for (i, j) in union]) // len(union)

        for (i, j) in union :
            graph[i][j] = p
    
    day += 1

print(day)

 

풀이 2

• 1. 입력 받기
• 2. 국경선 열기   
• 3. 인구수 정리하기

from collections import deque

def open_borders(x, y):
    nations = [(x, y)]    # 연합한 나라들 리스트
    
    q = deque([(x, y)])
    borders[x][y] = False

    populations = maps[x][y]    # 연합 전체 인구수
    count = 1   # 연합 국가 수

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]

            # 인근 나라와의 인구수 확인 (L명 이상 R명 이하)
            if 0 <= nx < N and 0 <= ny < N and borders[nx][ny]:
                if L <= abs(maps[x][y] - maps[nx][ny]) <= R :
                    q.append((nx, ny))
                    borders[nx][ny] = False       # 국경선 열림 표시 
                    populations += maps[nx][ny]   # 연합 인구수 더하기   
                    count += 1                    # 연합 국가수 더하기
                    nations.append((nx, ny))      # 연합 국가 추가
    
    for i, j in nations:
        maps[i][j] = populations // count
    
    return len(nations)

# 1. 입력 받기
N, L, R = map(int, input().split())     # 땅 크기, L명 이상 R명 이하
maps = []   # 각 땅의 인구 수
for _ in range(N):
    maps.append(list(map(int, input().split()))) 


# 2. 인구 이동 
dx = (-1, 1, 0, 0)  # 상하좌우
dy = (0, 0, -1, 1)
move_days = 0       # 인구 이동 일수

while True:
    borders = [ [ True for _ in range(N)] for _ in range(N) ]   # 국경선
    flag = False

    # 국경선 열고 인구 이동
    for i in range(N):
        for j in range(N):
            if borders[i][j] :
                country = open_borders(i, j)
                if country > 1:
                    flag = True
    
    # 모든 인구 이동 끝난 경우
    if not flag:
        break

    move_days += 1

print(move_days)

 

 

References

• 백준 그래프탐색