백준, 1012 유기농 배추 javascript

백준, 1012 유기농 배추

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

👨‍💻 문제 풀이

• bfs, dfs알고리즘 유형의 문제로 지금까지 풀어왔던 문제들과 똑같은 로직이다.
• 다만, input값에서 테스트케이스가 한번에 여러가지가 들어와서 map을 만들어놓고 각 map에 대한 정답을 출력해야하는 부분에서 고생했다.

💻 제출한 코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const TC = +input.shift();
let data = input;
const maps = [];

for(let i=0; i<TC; i++) {
    let [M, N, K] = data.shift().split(' ').map(Number);
    let map = Array.from({length: N}).map(row => row = Array.from({length:M}).fill(0));

    for(let i=0; i<K; i++) {
        let [X, Y] = [+data[i].split(' ')[0], +data[i].split(' ')[1]]
        map[Y][X] = 1;
    }
    maps.push(map);
    data.splice(0, K);
}
// TC를 구분해서, map을 구하는 부분

function solution(arr) {
    const visited = {};
    let answer = 0;
    for(let i=0; i<arr.length; i++) {
        for(let j=0; j<arr[0].length; j++) {
            if(arr[i][j] === 1 && !visited[[i,j]]) {
                bfs(i,j);
            }
        }
    }

    function bfs(x, y) {
        const queue = [[x, y]];
        const result = [];
        visited[[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++) {
                const coords = queue.shift();
                if(!visited[[coords[0], coords[1]]]) continue;
                result.push(coords);
                for(let j=0; j<4; j++) {
                    let nx = coords[0] + dx[j];
                    let ny = coords[1] + dy[j];
                    if((nx >= 0 &&
                        ny >= 0 &&
                        nx < arr.length &&
                        ny < arr[0].length) &&
                        (arr[nx][ny] === 1) &&
                        (!visited[[nx,ny]])
                    ) {
                        visited[[nx,ny]] = true;
                        queue.push([nx, ny]);
                    }
                }
            }
        }
        answer++;
    }

    return answer;
}
// 영역의 수를 출력해주도록 bfs함수를 살짝 고쳤다.
maps.forEach((farm) => {
    console.log(solution(farm));
})

이번 문제를 풀면서,

• map을 그리는게 힘들다.
• bfs알고리즘은 어느정도 익숙해졌지만 역시나, 다른사람들 코드와 비교해보면 약간 길다.
• bfs, dfs정리를 다시한번 할 타이밍이 된 것 같다.