1/16 Coding Test

✅ Coding Test

🎈 16234 인구 이동

NXN 크기의 땅이 있고 각 땅에는 나라가 하나씩 존재하며 r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다.

인구 이동은 오늘 하루 동안 다음과 같이 진행된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상 R명 이하라면 두 나라가 공유하는 국경선을 오늘 하루 연다.
• 위 조건에 의해 열어야 하는 국경선이 모두 열리면 인구 이동 시작
• 국경선이 열려 있어 인접한 칸만을 이동해 이동할 수 있으면 그 나라를 하루 동안 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 연합의 인구수 / 연합을 이루고 있는 칸의 개수가 된다. 편의상 소수점은 제외시킨다.
• 연합을 해체하고 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때 인구 이동이 며칠 동안 발생하는지 구하는 문제.

입력
첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)
인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력
인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

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

n, l, r = map(int ,input().split())
people = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def moving(i, j):
    queue = deque()
    queue.append((i, j))
    visited[i][j] = True
    fed = [(i, j)]
    person = people[i][j]
    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 l <= abs(people[nx][ny] - people[x][y]) <= r:
                    visited[nx][ny] = True
                    fed.append((nx, ny))
                    queue.append((nx, ny))
                    person += people[nx][ny]
    for a, b in fed:
        people[a][b] = person // len(fed)
    return len(fed)
    
answer = 0
while True:
    visited = [[False]*n for _ in range(n)]
    moving_day = False
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                if moving(i, j) > 1:
                    moving_day = True
    if not moving_day:
        break
    answer += 1

print(answer)

< 해설 >

BFS로 탐색을 하되 결국 문제에서 요구하는 사항을 출력하는 것을 기억해야 하는 문제.
구현에 있어 지정해주어야 할 것들을 생각하느라 시간이 좀 걸렸다.

문제를 푼 로직은 다음과 같다.

1. 우선, 주어진 입력값과 방향 이동을 위한 리스트 dx, dy를 지정한다.
2. moving 즉, 현 위치를 파라미터로 인구 이동하는 함수를 만들어 연합국을 찾고, 인구를 이동시킨다.
   2-1. 현 위치가 입력될 때 큐에 넣고 현 위치를 방문처리한다. 또한, 연합국 좌표를 위해 federation에 현 위치를 넣고, 인구수 계산을 위해 person 변수에 현 위치에 속한 나라의 인구수를 저장한다.
   2-2. 큐가 비지 않을 때까지 현 위치 기준 상하좌우 4방향 탐색을 하되 다음 조건을 만족하는 것에 한해 탐색을 진행한다.
   2-3. 다음 위치가 주어진 범위이고 방문하지 않은 곳이어야 하며 나라 간 인구 차이가 l과 r사이에 속한다면 다음 탐색을 진행한다.
   2-4. 앞선 조건을 만족하면 다음 위치도 방문처리하고 큐에 넣고 연합국 처리를 한 후 person 변수에 인구수를 더한다.
3. federation에 속하는 좌표들은 연합국이므로 인구수를 변경시킨 후 최종적으로 연합국 개수를 리턴한다.
4. 인구 이동이 지속되는 과정을 while loop로 표현하고 방문하지 않은 좌표 중 moving 함수 실현이 가능하면 인구 이동이 가능한 것이므로 moving_day = True로 전환한다.
5. while loop의 종료 조건은 인구 이동이 없는 경우이므로 not moving_day일때 종료시킨다.
6. 인구 이동을 한 횟수를 결과적으로 출력