[BOJ][🟡5][백준#16234] 인구 이동

문제 출처

BAEKJOON Online Judge #16234

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

국경선을 공유하는 두 나라의 인구 차이가 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번 보다 작거나 같은 입력만 주어진다.

출력

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

예제

예제 1

입력

2 20 50
50 30
20 40

출력

1

예제 2

입력

2 40 50
50 30
20 40

출력

0

예제 3

입력

2 20 50
50 30
30 40

출력

1

예제 4

입력

3 5 10
10 15 20
20 30 25
40 22 10

출력

2

예제 5

입력

4 10 50
10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10

출력

3

My Sol

def findUnion(i, j):
    global visited, N, L, R, POP
    visited[i][j] = 1
    unionQ = [(i, j)]
    start = -1
    end = 1

    while start < end-1:
        start += 1
        ni, nj = unionQ[start]

        # 상하좌우 탐색
        didj = [(-1,0),(0,-1),(1,0),(0,1)]
        for di, dj in didj:
            # 탐색 좌표가 범위 내에 있고,
            if 0<=ni+di<N and 0<=nj+dj<N:
                # 방문하지 않았던 곳이며,
                if not visited[ni+di][nj+dj]:
                    # 현재 위치의 인구수 차이가 L 이상 R 이하라면
                    if L <= abs(POP[ni][nj] - POP[ni+di][nj+dj]) <= R:
                        # visited에 반영하고 unionQ에 추가
                        visited[ni+di][nj+dj] = 1
                        unionQ.append((ni+di, nj+dj))
                        end += 1
    return unionQ



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

while True:
    visited = [[0]*N for _ in range(N)]
    unions = []
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                union = findUnion(i, j)
                # union이 2 국가 이상일 때만 unions에 union 추가
                if len(union) > 1:
                    unions.append(union)

    # 종료조건 : unions가 없으면 인구 이동 없음
    if not unions:
        break

    # POP2 생성
    POP2 = []
    for lst in POP:
        POP2.append(lst[::])

    # 연합 별 POP2에 인구 재분배
    for union in unions:
        # 연합 내 나라 수, 인구 합계 계산
        sum_pop = 0
        cnt = 0
        for country in union:
            ci, cj = country
            sum_pop += POP[ci][cj]
            cnt += 1

        # 연합 내 인구 재분배
        avg_pop = sum_pop // cnt
        for country in union:
            ci, cj = country
            POP2[ci][cj] = avg_pop

    # POP2를 POP으로 갱신(얕은 복사 가능)
    POP = POP2

    # 결과 + 1
    ret += 1

print(ret)

생각했던대로 풀 수 있던 문제였고, 어려운 문제들을 풀고와서 그런가 그렇게 어렵게 느껴지지는 않았던 문제였다.

문제 풀이 전개 방식

1. 입력을 받아 처리
2. visited 2차원 배열로 모든 좌표에 대해 완전 탐색
3. visited가 0인 경우 해당 좌표부터 상하좌우 확인하여 연합 가능 국가 체크
4. 범위 내이고, 방문하지 않았으며, 연합이 가능하다면, 연합에 추가(visited도 체크)
5. BFS : 연합에 추가된 국가 좌표 기준으로 상하좌우를 조회하며 모든 가능한 연합에 대한 Queue 채우기
6. 함수 외부에 Union Queue를 전달하고, 이를 union 내부 국가가 2개 이상이라면 unions 배열에 추가
7. 2~6번을 반복하며 visited 모두 조회
8. unions의 각 union의 국가 좌표로 평균 인구 수 계산하여 별도의 2차원 배열에 넣기
9. 인구 이동 횟수 1 증가
10. 1~9 반복 : 종료 조건은 어떠한 국가와도 서로 인구 이동이 가능하지 않아 unions가 빈(False) 경우

BFS를 이용하여 가능한 연합을 조회하는 함수 findUnion() 함수를 별도로 작성하여 visited 조회와 Union 탐색이 가시적으로 분리되도록 작성하였다. 코드별 자세한 설명은 주석 참고.

결과

맞았습니다!!