[백준] 16234. 인구이동 풀이 (Python, JavaScript)

16234번: 인구 이동

접근한 방법

매 반복문을 돌며 BFS를 이용해 조건에 맞는 좌표를 후보지에 등록해두고 탐색이 끝나면 등록된 후보지들의 인구 수를 한꺼번에 변경해주는 방식으로 구현합니다.

 

1. while 문을 이용해 인구 이동 횟수를 카운트합니다.

2. 연합이 가능한 위치들을 넣을 후보 배열을 만들고 방문하지 않은 위치에 대하여 탐색을 시도합니다.

3. BFS탐색을 시도하여 방문하지 않았고 절댓값 차이가 L과 R 사이 값을 만족하는 위치가 있는 곳을 확인하여 후보지에 넣어줍니다.

4. 모든 위치에 대하여 BFS종료 후 후보지에 들어있는 위치들을 순회하여 각 연합에서 계산한 인구수 평균을 계산해 원본 배열을 갱신합니다.

5. 2~4를 반복 후 더이상 후보가 없는 경우 while을 순회한 횟수를 리턴합니다.

 

Python

import sys
sys.stdin = open("input.txt", "r") # 제거
input = sys.stdin.readline

n, l, r = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
result = 0
dir = ((-1, 0), (1, 0), (0, -1), (0, 1))
from collections import deque

# 연합 후보 위치 탐색
def transfer(sr, sc, visited):
    q = deque()
    q.append((sr, sc))
    targets = [(sr, sc)] # 연합할 타겟 좌표들
    targets_sum = arr[sr][sc] # 연합 인구 합
    while q:
        qr, qc = q.popleft()
        for [x, y] in dir:
            dr, dc = qr + x, qc + y
            # 맵 밖이거나 이미 방문한 경우
            if dr < 0 or dc < 0 or dr >= n or dc >= n:
                continue
            if visited[dr][dc]:
                continue
            diff = abs(arr[qr][qc] - arr[dr][dc])
            # 탐색 위치와 현재 위치와의 절댓값이 L이상 R이하이면 타겟 좌표로 등록
            if diff >= l and diff <= r:
                visited[dr][dc] = 1
                targets.append((dr, dc))
                targets_sum += arr[dr][dc]
                q.append((dr, dc))
    return [targets, targets_sum]

# 이동 횟수 카운트
while 1:
    visited = [[0] * n for _ in range(n)]
    candidates = [] # 연합에 넣을 좌표 후보
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                visited[i][j] = 1
                targets, targets_sum = transfer(i, j, visited) # 연합할 타겟 좌표들, 연합 인구 합
                # 2곳 이상의 연합이 생기면 후보에 넣음
                if len(targets) > 1:
                    candidates.append([targets, targets_sum])
    # 후보가 없을 경우 종료
    if not candidates:
        print(result)
        break
    for [targets, target_sum] in candidates:
        size = target_sum // len(targets) # 연합 인구 수 평균
        for [tr, tc] in targets:
            arr[tr][tc] = size
    result += 1

JavaScript

function solution(n, l, r, arr) {
  let result = 0;
  const dir = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  const transfer = (sr, sc, visited) => {
    const q = [[sr, sc]];
    let front = 0;
    const targets = [[sr, sc]];
    let targetsSum = arr[sr][sc];

    while (q[front]) {
      const [qr, qc] = q[front++];
      for (const [x, y] of dir) {
        const [dr, dc] = [qr + x, qc + y];
        if (dr < 0 || dc < 0 || dr >= n || dc >= n) continue;
        if (visited[dr][dc]) continue;

        const diff = Math.abs(arr[qr][qc] - arr[dr][dc]);
        if (diff >= l && diff <= r) {
          visited[dr][dc] = 1;
          targets.push([dr, dc]);
          targetsSum += arr[dr][dc];
          q.push([dr, dc]);
        }
      }
    }
    return [targets, targetsSum];
  };
  while (1) {
    const visited = Array.from({ length: n }, () => Array(n).fill(0));
    const candidates = [];
    for (let i = 0; i < n; i += 1) {
      for (let j = 0; j < n; j += 1) {
        if (!visited[i][j]) {
          visited[i][j] = 1;
          const [targets, targetsSum] = transfer(i, j, visited);
          if (targets.length > 1) candidates.push([targets, targetsSum]);
        }
      }
    }
    if (!candidates[0]) return result;
    for (const [targets, targetsSum] of candidates) {
      const size = parseInt(targetsSum / targets.length);
      for (const [tr, tc] of targets) arr[tr][tc] = size;
    }
    result += 1;
  }
}
console.log(
  solution(3, 5, 10, [
    [10, 15, 20],
    [20, 30, 25],
    [40, 22, 10],
  ])
);