알고리즘

[백준] 16234 인구 이동 - 골드 4

swanzzz 2025. 4. 16. 23:53
반응형

[오늘의 문제]

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


[오늘의 학습 키워드]

  • BFS, 구현, 시뮬레이션

1. 문제 설명

 

문제를 보면 현재 지역을 기준으로 인접한 국경이 열리는 경우와 그렇지 않은 경우가 있습니다.

 

주어진 N x N 배열에서 인접한 위치가 열리는 경우는 현재 위치와 인접한 위치의 인구 수 차이가 주어진 L, R 의 차이 이내인 경우 입니다.

 

즉 0, 0 위치의 인구수 50 과 0, 1 위치의 인구수 30의 차이가 20으로 주어진 L, R 20 이상 50 이하의 조건에 만족하니 인구 이동이 가능한 국경이 열리고, 국경이 열린 경우 인구 이동을 실시하는데 모든 열린 국경을 탐색한 후 인구 이동을 실시합니다.

 

인구 이동이 가능한 횟수를 구하는 문제입니다.


[제한 사항]

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

2. 접근 방식

 

전체 탐색을 실시하며 현재 위치를 기준으로 국경이 열린 지역을 먼저 모두 찾습니다.

 

국경이 열린 지역을 모두 찾았으면 인구 이동을 실시해 주면 됩니다.

 

이때 주의할 것은 다음과 같은 경우 입니다.

 

2 20 20
50 30
20 40

 

으로 N, L, R 이 주어지는 경우 입니다.

 

전체 탐색을 실시할 때 현재 위치 0, 0을 기준으로 국경이 열리는 지역은 0, 1 뿐입니다.

 

이때 국경이 열리고 인구 이동을 실시하면 

40 40
20 40

 

이 됩니다.

그 다음 인구 이동이 가능한 지역은 1, 0 위치의 20이 됩니다.

 

이러면 틀리게 됩니다.

 

전체 탐색을 실시할때 국경이 열리는 지역을 연합국이라고 하는데 이 연합국은 2개가 될 수도 있습니다.

 

위 경우 연합국은 2개가 발생하여 1번의 인구 이동으로

40 40
30 30

이 나와야 됩니다.

 

즉 연합이 발생한 경우 바로 인구 이동을 실시하는게 아니고, 인구 이동이 발생하는 경우를 모두 찾고, 연합도 모두 찾은뒤

그 다음 인구 이동을 실시해 주어야 합니다.

 

이를 유의하며 코드를 작성하였습니다.


3. 코드

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

# 4방향 탐색
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def BFS(x, y):
    queue = deque([(x, y)])     # 시작 위치 저장
    queue2 = deque([(x, y)])    # 인구 이동 처리 위한 queue2
    people = world[x][y]        # 인구 이동 처리 위한 people
    visited[x][y] = True        # 시작 위치 방문 처리

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

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

            # 조건 범위 안, 미방문 지역, L <= 차이 <= R 인 경우
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                if L <= abs(world[x][y] - world[nx][ny]) <= R:
                    queue.append((nx, ny))      # queue 넣기
                    queue2.append((nx, ny))     # 정답큐에 넣기
                    people += world[nx][ny]     # 인구수 증가
                    visited[nx][ny] = True      # 방문 처리
    
    # 시작 위치를 제외하고 정답큐가 2 이상인 경우
    if len(queue2) > 1:
        people = people // len(queue2)
        while queue2:
            x, y = queue2.popleft()
            copy_world[x][y] = people   # 인구 이동 실시

# 입력
N, L, R = map(int, input().split())
world = [list(map(int, input().split())) for _ in range(N)]

# 인구 이동 횟수
answer = 0

# 최대 2000번 주어진다함
while answer <= 2000:
    visited = [[False] * N for _ in range(N)]   # 방문 처리 배열
    copy_world = deepcopy(world)                # 4%에서 틀림 -> 연합이 있는 경우 바로 인구 이동 실시 -> 인구 이동을 저장할 deepcopy 배열

    # 전체 탐색하며 BFS 실시
    for i in range(N):
        for j in range(N):
            BFS(i, j)
    
    # 전체 탐색의 결과가 이전과 같으면 출력 후 종료
    if world == copy_world:
        print(answer)
        exit()
    
    # 다르면 world 초기화 후 정답 증가
    else:
        world = copy_world
        answer += 1

[코드 설명]

# 입력
N, L, R = map(int, input().split())
world = [list(map(int, input().split())) for _ in range(N)]

# 인구 이동 횟수
answer = 0

# 최대 2000번 주어진다함
while answer <= 2000:
    visited = [[False] * N for _ in range(N)]   # 방문 처리 배열
    copy_world = deepcopy(world)                # 4%에서 틀림 -> 연합이 있는 경우 바로 인구 이동 실시 -> 인구 이동을 저장할 deepcopy 배열

    # 전체 탐색하며 BFS 실시
    for i in range(N):
        for j in range(N):
            BFS(i, j)
    
    # 전체 탐색의 결과가 이전과 같으면 출력 후 종료
    if world == copy_world:
        print(answer)
        exit()
    
    # 다르면 world 초기화 후 정답 증가
    else:
        world = copy_world
        answer += 1

 

입력을 받고 인구 이동 횟수를 구하기 위한 answer를 선언한 뒤 while문으로 반복을 실시합니다.

 

인구 이동이 최대 2000번 이하로만 주어진다고 했으니 while문의 조건을 다음과 같이 작성하였고

 

전체 탐색을 실시하며 BFS 탐색을 실시합니다.

 

이때 BFS 탐색 후 인구 이동의 결과를 저장하기 위해서 기존의 world 배열을 복사한 copy_world 를 선언해 주었고 인구 이동의 결과를 이 copy_world에 저장해 주었습니다.

 

BFS 탐색이 종료되었는데, 현재 world와 복사 후 인구 이동이 발생한 copy_world가 동일한 경우 이 경우는 인구 이동이 발생하지 않은 경우이니 바로 answer를 출력후 종료해주었고 

 

그게 아니라면 world를 초기화 시키며 answer 횟수를 증가시켜 주었습니다.


# 4방향 탐색
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def BFS(x, y):
    queue = deque([(x, y)])     # 시작 위치 저장
    queue2 = deque([(x, y)])    # 인구 이동 처리 위한 queue2
    people = world[x][y]        # 인구 이동 처리 위한 people
    visited[x][y] = True        # 시작 위치 방문 처리

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

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

            # 조건 범위 안, 미방문 지역, L <= 차이 <= R 인 경우
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                if L <= abs(world[x][y] - world[nx][ny]) <= R:
                    queue.append((nx, ny))      # queue 넣기
                    queue2.append((nx, ny))     # 정답큐에 넣기
                    people += world[nx][ny]     # 인구수 증가
                    visited[nx][ny] = True      # 방문 처리
    
    # 시작 위치를 제외하고 정답큐가 2 이상인 경우
    if len(queue2) > 1:
        people = people // len(queue2)
        while queue2:
            x, y = queue2.popleft()
            copy_world[x][y] = people   # 인구 이동 실시

 

시작위치를 입력받고 queue에 넣어주는데 queue는 2개 선언해 주었습니다.

 

1번은 너비 우선 탐색을 실시하며 인접한 열린 국경을 찾기 위한 queue

 

2번은 국경의 좌표 정보를 저장할 queue2 입니다.

 

현재 위치를 방문 처리하며 현재 나라의 인구수를 people에 저장해 주었습니다.

 

4방향 탐색을 실시하며, 조건에 맞춰 queue를 초기화 해주었습니다.

 

조건은 아직 방문하지 않은 국가여야 하고, 국경이 열려있어야 합니다.

 

국경이 열리는 조건은 현재 나라와 다음 나라의 인구수 차이가 L 이상 R 이하 여야 하므로 이 조건을 맞추기 위해 abs를 활용해 결

 

과를 계산해 주었고 이 경우를 만족하면 queue에 너비 우선 탐색을 위해 다음 위치를 넣고, 방문처리를 실시해 주었습니다.

 

또 정답 처리를 위해 queue2 에도 위치 정보를 넣고, 인구수도 증가시켜 주었습니다.

 

모든 연합국을 찾았다면 queue2에는 최소 2개 이상의 나라가 담겨있어야 하니 이 경우에만 해당 나라의 인구 이동을 실시해 주었습니다.


4. 결과


[회고]

처음에 틀렸던 이유가 4%에서 틀렸었는데 연합국을 찾자마자 바로 인구이동을 실시해서 틀렸었습니다.

 

질문 게시판에서 그 조건을 찾은 뒤 알맞게 구현할 수 있었고 다음 시도에서 바로 맞았는데 시간초가 너무 오래 걸렸습니다.

 

copy를 활용하는게 문제같아 다른 방식을 찾아 보고자 했는데 다른 사람의 경우 flag를 활용하여 기존의 배열을 업데이트 하였습니다.

 

근데 제가 작성한 코드도 크게 다른게 없어 여러 시도를 해보고 마지막으로 PyPy로 실시해 보았는데 시간초가 비슷했습니다.

 

결국 정의한 함수를 실행하고, 배열을 복사하는 과정에서 시간초가 걸릴 수는 있겠지만 주어진 입력 조건이 최대 50x50 크기의 배열이라 크게 신경쓰지는 않았습니다.

 

결국 문제는 전체 탐색을 하며 BFS의 실행여부에 따라 시간초가 다르게 걸렸고, 기존의 코드도 가지치기가 잘 이루어진 코드라 그대로 제출하였습니다.

 

물론 함수를 정의하지 않고 한번의 while문 동작에서 함수에 작성한 코드를 바로 실행하는 편이 더 빠를 수는 있겠지만

 

가독성을 위해 그렇게 하지는 않았습니다.

 

반응형