백준, 2468 안전 영역 javascript

백준,2468 안전 영역

📖 https://www.acmicpc.net/problem/2468

👨‍💻 문제 풀이

• 이번에도 bfs를 활용했다.
• bfs는 가능한 만큼의 끝까지 탐색하게 된다.
• 특정 target을 정해 놓고, 모든 좌표를 순회하는 방법으로 풀었다.

💻 제출한 코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input.shift();
const map = input.map((row) => row = row.split(' ').map(Number));


let max;
map.forEach((row) => {
    max = Math.max(...row);
})

function bfs(x,y, target, visisted) {
  // 이번에는 이렇게 매개변수로 visited를 받았다. 
    const queue = [[x,y]];
    const result = [];
    visisted[[x,y]] = true;
    let dx = [0, 0, -1, 1];
    let dy = [-1, 1, 0, 0];

    while(queue.length) {
        for(let i=0; i<queue.length; i++) {
            let coord = queue.shift();
            result.push(coord);

            for(let j=0; j<4; j++) {
                let nx = coord[0] + dx[j];
                let ny = coord[1] + dy[j];

                if(( nx >= 0 &&
                    ny >= 0 &&
                    nx < N &&
                    ny < N) &&
                    map[nx][ny] > target &&
                   // 특정 target을 넘었을 때에만 큐에 푸시한다.
                    !visisted[[nx,ny]]
                ) {
                    visisted[[nx,ny]] = true;
                    queue.push([nx, ny]);
                }
            }
        }
    }
}


// 출력부분
let answer = Number.MIN_SAFE_INTEGER;
for(let k=0; k<=max; k++) {
    const visisted = {};
    let cnt = 0;
    for(let i=0; i<N; i++) {
        for(let j=0; j<N; j++) {
            if(map[i][j] > k && !visisted[[i,j]]) {
                bfs(i,j,k,visisted);
              // bfs는 탐색할수 있는 부분까지 탐색하고 멈춘다.
              // bfs탐색이 한번 끝났다는 것은 안전영역이 한개 늘어났다는 것과 동일하다.
                cnt++;
            }
        }
    }
    if(answer < cnt) answer = cnt;
}

console.log(answer)

이번 문제를 풀면서,

• 이 코드 엄청 느리다.
• 효율성을 신경 쓸 필요가 생겼다.
• 지금까지 문제를 풀면서, 백준의 맞힌사람중에 제일 느린 경험을 해본적은 없었는데 이번 문제는 문제풀이 방식에서 거의 꼴지를 다투고 있다.
• 어디가 문제일까에 대해 진지하게 고민해 볼 필요가 있다.