[백준] 16234 인구 이동 (Javascript)

문제

BOJ16234_인구 이동

풀이

문제 정의

N * N 크기의 맵이 있고, 한 칸은 하나의 국가를 나타내고 칸 안에는 해당 국가의 인구수가 적혀있다.
그리고 하루마다 아래와 같은 과정이 일어난다.

• 인접한 국가 끼리 인구수의 차이가 L이상 R이하면 서로 국경을 개방한다.
• 국경이 개방된 나라끼리는 서로 연합이 되고, 조건에 맞는 국가들의 국경이 전부 개방되었다면 연합국끼리 인구 분배를 시작한다.
• 인구 분배를 수행하고 나면 연합의 각 나라의 인구수는 (연합국의 총 인구수) / (연합국의 수)가 된다. (소수점은 버린다.)
• 국경을 전부 닫는다.

이 과정을 인구 분배를 할 수 없을 때까지 반복했을 때, 며칠이 걸리는지를 구하는 문제다.

해결방안

우선 인접한 국가끼리 인구수의 차이가 L이상 R이하인지 확인하려면 우선 인접한 국가를 확인하는 로직이 필요하다.

이는 BFS를 이용하여 상,하,좌,우를 확인해주며, 인접한 칸에 있는 인구 수와 현재 칸의 인구수의 차이가 L이상 R이하인지 확인하면 된다.

function bfs(y, x) {
    const queue = [[y, x]];
    visited[y][x] = true;
    let front = 0;
    while (queue.length > front) {
        const [y, x] = queue[front++];
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[ny][nx]) {
                const diff = Math.abs(arr[y][x] - arr[ny][nx]); // 옆 국가와 인구수 차이
                const distribute = diff >= L && diff <= R; // 인구수 차이가 L이상 R이하인가?
                if (distribute) {
                    queue.push([ny, nx]);
                    visited[ny][nx] = true;
                }
            }
        }
    }
}

또한 인구 분배를 해주려면 "연합의 총 인구수"와 "연합국의 수"를 누적해야 한다.
따라서 코드를 아래와 같이 추가해준다.

function bfs(y, x) {
  ...
  let population = arr[y][x];
  let nations = 1;
    while (queue.length > front) {
      	...
                if (distribute) {
                  ...
                    population += arr[ny][nx];
                    nations++;
                }
            }
        }
    }
}

while문이 종료되었을 때 queue에는 연합국들의 인덱스가 저장되어있을 것이다.

따라서 "연합의 총 인구수" / "연합국의 수"를 한 결과를 연합국에 각각 할당해준다.

function bfs(y, x) {
    ...
    while (queue.length > front) {
       ...
    }
    // 칸 당 인구수
    const per = Math.floor(population / nations);
    // 인구 분배
    for (const [y, x] of queue) {
        arr[y][x] = per;
    }
}

한 번의 bfs가 종료되면 한 덩어리의 연합에 인구 분배가 이루어진 것이다. 하지만 아직 인구 분배가 필요한 다른 연합이 있을 수 있으므로 맵 전체를 탐색해주며 방문하지 않은 칸에 대해서 bfs를 수행해줘야 한다.

for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (!visited[i][j]) bfs(i, j);
  }
}

저렇게 2중 for문이 종료되면 그제야 하루가 지난 것이다.
따라서 하루가 지났을 때 인구 분배가 이루어졌다면 카운트를 증가시킨다.

function bfs(y, x) {
  ...
    while (queue.length > front) {
      ...
                if (distribute) {
                  ...
                    isDistributed = true;
                }
            }
        }
    }
  ...
}
  
let answer = 0;
let isDistributed = false;
for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (!visited[i][j]) bfs(i, j);
    }
  }
  // 인구 분배가 일어났다면 카운트 증가
  if (isDistributed) {
    answer++;
    isDistributed = false;
  } else break;
}

이 과정을 인구 분배가 일어나지 않을 때까지 반복해야 하고, 하루가 지나면 다시 새로운 인구 분배를 해야하기 때문에 visited 배열도 초기화해줘야 한다.

while (true) {
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (!visited[i][j]) bfs(i, j);
        }
    }
    if (isDistributed) {
      ...
        visited.forEach((row) => row.fill(0));
    } else break;
}

전체 코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, L, R] = input[0].split(' ').map(Number);
const arr = input.slice(1, 1 + N).map((e) => e.split(' ').map(Number));
const visited = Array.from(Array(N), () => Array(N).fill(false));

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

function bfs(y, x) {
    const queue = [[y, x]];
    visited[y][x] = true;
    let front = 0;
    let population = arr[y][x];
    let nations = 1;
    while (queue.length > front) {
        const [y, x] = queue[front++];
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[ny][nx]) {
                const diff = Math.abs(arr[y][x] - arr[ny][nx]); // 옆 국가와 인구수 차이
                const distribute = diff >= L && diff <= R; // 인구수 차이가 L이상 R이하인가?
                if (distribute) {
                    queue.push([ny, nx]);
                    visited[ny][nx] = true;
                    isDistributed = true;
                    population += arr[ny][nx];
                    nations++;
                }
            }
        }
    }
    // 칸 당 인구수
    const per = Math.floor(population / nations);
    // 인구 분배
    for (const [y, x] of queue) {
        arr[y][x] = per;
    }
}

let answer = 0;
let isDistributed = false;
while (true) {
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (!visited[i][j]) bfs(i, j);
        }
    }
    if (isDistributed) {
        answer++;
        visited.forEach((row) => row.fill(0));
        isDistributed = false;
    } else break;
}

console.log(answer);

시간 복잡도 (빅오 표기법의 한계)

이 코드의 시간복잡도는 $O(N^2)$이다.
그럼에도 불구하고 시간이 오래 걸린다.
우선 왜 $O(N^2)$인지부터 알아보자.

전형적인 bfs,dfs는 이미 방문했던 칸은 다시 방문하지 않기 때문에 칸의 개수는 최대 $N^2$ 이므로 최대 $O(N^2)$이라고 볼 수 있다. 하지만 위 코드에서 bfs 함수는 종료 전에 방문했던 칸을 다시 확인하는 과정이 있기 때문에 정확히는 $O(2N^2)$이다. 그러나 빅오 표기법 특성상 상수항이 제거되어 $O(N^2)$이 된다.

문제에서 일수는 최대 2000보다 작거나 같다고 나와있기 때문에 while은 최대 2000번 반복을 수행한다. while문의 반복 횟수를 'M' 이라고 정의하자.
이 상태로 시간복잡도를 계산해보면 bfs를 수행하기 전까지만 해도 $2000 \times 50 \times 50$ 번의 연산을 수행하고, bfs에서 $50 \times 50$ 의 연산을 수행하니 총 $2000 \times 50^4$ 으로 시간초과가 아닌가 의구심이 들 수 있다.

하지만 bfs를 수행하기 전 2중 for문에서 if (!visited[i][j]) 를 체크해서 조건부로 bfs를 수행하기 때문에, 이미 그 전 bfs에서 방문한 칸을 만났을 때는 또다시 bfs를 수행하지는 않는다.

즉, 실제로는 $(2중 for문+ bfs) = O(N^2)$로 봐도 될 것이다. 이를 while문이 감싸고 있고, 이 안에서 visited배열을 매번 초기화 해주기 때문에 시간복잡도는 $O(2N^2M)$이 되지만 빅오 표기법의 특성상 상수항이 제거되므로 시간 복잡도는 $O(N^2M)$이 된다.

N이 작을 때는 상수항의 영향이 크지만 빅오 표기법은 이러한 점을 고려하지 않기 때문에 N이 작을 때는 빅오 표기법으로 표현한 시간복잡도가 정확하지 않을 수 있다.

실제로 상수항을 전부 포함해서 계산을 해보면 약 $2000 \times 2\times2\times50^2=20,000,000$번으로 꽤 많은 연산을 수행할 것으로 보인다.

개선

코드를 다 풀고 맞힌 사람들의 코드를 봤는데, 시간이 훨씬 빠른 코드가 있어서 이를 적용해보았다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, L, R] = input[0].split(' ').map(Number);
const arr = input.slice(1, 1 + N).map((e) => e.split(' ').map(Number));
const flags = Array.from(Array(N), () => Array(N).fill(0));
const per = Array(N * N + 1).fill(0);
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

let answer = 0;
let isDistributed = false;
let union = 1;
let population;
let nations;

function dfs(y, x) {
    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < N && ny < N && flags[ny][nx] === 0) {
            const diff = Math.abs(arr[y][x] - arr[ny][nx]); // 옆 국가와 인구수 차이
            const distribute = diff >= L && diff <= R; // 인구수 차이가 L이상 R이하인가
            if (distribute) {
                flags[ny][nx] = union;
                dfs(ny, nx);
                isDistributed = true;
                population += arr[ny][nx];
                nations++;
            }
        }
    }
}

while (true) {
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (flags[i][j] === 0) {
                population = arr[i][j];
                nations = 1;
                flags[i][j] = union;
                dfs(i, j);
                // 칸 당 인구수
                per[union] = Math.floor(population / nations);
                union++;
            }
        }
    }
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            arr[i][j] = per[flags[i][j]];
        }
    }
    if (isDistributed) {
        answer++;
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < N; j++) {
                flags[i][j] = 0;
                per[i * N + j] = 0;
            }
        }
        isDistributed = false;
        union = 1;
    } else break;
}

console.log(answer);

이 코드의 특징은 bfs 대신 dfs를 사용함으로써 큐에 사용될 메모리를 더 아낄 수 있고, 큐에 저장된 연합의 정보 대신 flag 배열에 같은 같은 연합끼리 같은 번호로 지정해놓고 per 배열에 연합의 분배 인구(?)를 구한다. 즉 flag[i][j] === 1 이라면 (i,j)에 위치한 국가는 1번 연합에 소속된 것이고, 인구 이동이 한 차례 끝났을 때 per[i]에는 i 연합에 분배할 인구 수가 들어있다.

하지만 의문인 점은 내가 보기에 두 코드는 시간복잡도 상 차이가 거의 없을 것 같은데 아래 코드가 훨씬 빠르다는 것이다.

처음에 생각해본 것은 "큐를 이용해서 2차원 배열을 이용하기 때문에 참조 지역성의 원리로 인해 더 느리게 동작하나?" 생각했고 이를 검증하기 위해 위 코드의 per배열을 2차원 배열로 바꿔서 제출해보았다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, L, R] = input[0].split(' ').map(Number);
const arr = input.slice(1, 1 + N).map((e) => e.split(' ').map(Number));
const flags = Array.from(Array(N), () => Array(N).fill(0));
const per = Array.from(Array(N), () => Array(N).fill(0));
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

let answer = 0;
let isDistributed = false;
let union = 1;
let population;
let nations;

function dfs(y, x) {
    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < N && ny < N && flags[ny][nx] === 0) {
            const diff = Math.abs(arr[y][x] - arr[ny][nx]); // 옆 국가와 인구수 차이
            const distribute = diff >= L && diff <= R; // 인구수 차이가 L이상 R이하인가
            if (distribute) {
                flags[ny][nx] = union;
                dfs(ny, nx);
                isDistributed = true;
                population += arr[ny][nx];
                nations++;
            }
        }
    }
}

while (true) {
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (flags[i][j] === 0) {
                population = arr[i][j];
                nations = 1;
                flags[i][j] = union;
                dfs(i, j);
                // union번 연합에 분배되어야 할 인구 수
                per[Math.floor((union - 1) / N)][(union - 1) % N] = Math.floor(population / nations);
                union++;
            }
        }
    }
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (flags[i][j] === 0) continue;
            arr[i][j] = per[Math.floor((flags[i][j] - 1) / N)][(flags[i][j] - 1) % N];
        }
    }
    if (isDistributed) {
        answer++;
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < N; j++) {
                flags[i][j] = 0;
                per[i][j] = 0;
            }
        }
        isDistributed = false;
        union = 1;
    } else break;
}

console.log(answer);

이전 코드보다 느려진 것은 맞지만 아직도 처음 코드보단 월등히 빠르다. 어떤 부분에서 이런 속도차이가 발생한 것일까?