[백준] 5549 행성 탐사 (Javascript)

문제

BOJ5549_행성 탐사

풀이

단순하지만 시간초과

떠올리기 쉽고 가장 단순한 방법은 브루트 포스로 푸는 방식이다.

for(let k=0; k<K; k++){
	const [a,b,c,d] = input[k];
  	for(let i=a; i<=c; i++){
    	for(let j=b; j<=d; j++){
        	// J,O,I 경우에 따라 카운트 증가
        }
    }
}

위와 같이 브루트 포스 방식으로 탐색한다면 $O(KNM)$의 시간이 걸리고 시간 초과가 나오기 때문에 다른 방법을 찾아야 한다.

누적합(DP)

위와 같은 지도가 주어졌다고 했을 때, 각각의 칸에 J,O,I의 개수를 누적해주면 된다.
이를 구하는 식은 dp[i][j][k] = dp[i][j - 1][k] + dp[i - 1][j][k] + arr[i][j][k] - dp[i - 1][j - 1][k] 이다.
예를 들어 4번 칸에 값을 누적한다고 했을 때, 현재 값에 2번에 있는 누적값과 3번에 있는 누적값을 더하고 1번에 있는 누적값을 빼주면 된다. 여기서 1번의 누적값을 빼주는 이유는 3번의 누적값을 구할 때와 2번의 누적값을 구할 때, 둘다 1번이 더해지기 때문에 1번을 빼주지 않으면 1번이 두 번 더해지는 셈이기 때문에 이를 막기 위해 빼주는 것이다.

이렇게 누적값을 채우면 4번에는 1+2+3+4번에 있는 값들이 모두 누적되고 이 방식은 $O(NM)$의 시간으로 통과할 수 있다.

const dp = Array.from({ length: M + 1 }, () => Array.from({ length: N + 1 }, () => Array(3).fill(0)));

for (let i = 1; i <= M; i++) {
    for (let j = 1; j <= N; j++) {
        for (let k = 0; k < 3; k++) {
            dp[i][j][k] = dp[i][j - 1][k] + dp[i - 1][j][k] + arr[i][j][k] - dp[i - 1][j - 1][k];
        }
    }
}

이렇게 배열에 누적값을 채워줬으면 이제 조사해야될 좌표 (a,b),(c,d)에 맞춰서 결과를 도출해야 한다.

아래의 배열을 보자.

이때 a,b,c,d가 각각 2,2,3,3으로 주어졌다고 가정해보면 아래와 같이 (2,2)부터 (3,3)까지의 누적합을 구할 수 있다.

for (let [a, b, c, d] of area) {
    for (let k = 0; k < 3; k++) {
        answer += `${dp[c][d][k] - (dp[c][b - 1][k] + dp[a - 1][d][k] - dp[a - 1][b - 1][k])} `;
    }
    answer += `\n`;
}

코드

// N=가로, M=세로
// (dp[i][j][0] = J = 정글, dp[i][j][1] = O = 바다, dp[i][j][2] = I = 얼음)
// 1. 중첩 반복문을 통해 (a,b) 부터 (c,d)까지 K번 탐색하기 = O(KNM) = 시간초과
// 2. dp[i][j][k] = dp[i][j - 1][k] + dp[i - 1][j][k] + arr[i][j][k] - dp[i - 1][j - 1][k];
//    O(NM) = 통과

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [M, N] = input[0].split(' ').map(Number);
const K = +input[1];
const map = input.slice(2, M + 2).map((e) => e.split(''));
const area = input.slice(M + 2).map((e) => e.split(' ').map(Number));
const arr = Array.from({ length: M + 1 }, () => Array.from({ length: N + 1 }, () => Array(3).fill(0)));
for (let i = 0; i < M; i++) {
    for (let j = 0; j < N; j++) {
        if (map[i][j] === 'J') arr[i + 1][j + 1][0] = 1;
        else if (map[i][j] === 'O') arr[i + 1][j + 1][1] = 1;
        else if (map[i][j] === 'I') arr[i + 1][j + 1][2] = 1;
    }
}
const dp = Array.from({ length: M + 1 }, () => Array.from({ length: N + 1 }, () => Array(3).fill(0)));

for (let i = 1; i <= M; i++) {
    for (let j = 1; j <= N; j++) {
        for (let k = 0; k < 3; k++) {
            dp[i][j][k] = dp[i][j - 1][k] + dp[i - 1][j][k] + arr[i][j][k] - dp[i - 1][j - 1][k];
        }
    }
}

let answer = '';
for (let [a, b, c, d] of area) {
    for (let k = 0; k < 3; k++) {
        answer += `${dp[c][d][k] - (dp[c][b - 1][k] + dp[a - 1][d][k] - dp[a - 1][b - 1][k])} `;
    }
    answer += `\n`;
}
console.log(answer.trimEnd());