백준, 2583 영역구하기 javascript

백준, 2583 영역구하기 javascript

📖 https://www.acmicpc.net/problem/2583!

👨‍💻 문제

문제 풀이

• 이번 문제는, 지금까지 구했던 bfs로 무난히 풀 수 있다.
• 그런데, 문제는 주어지는 배열의 좌표가 배열의 좌표랑 일치 하지 않아서 새로운 map을 만들어 줘야 한다는 것이 문제였다.

map 만들기

💻 제출한 코드

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


const [M, N, K] = input.shift().split(' ');


// 세로 M, 가로 N 짜리 0으로 채워진 이차원 배열 만들기.

let arr = Array.from({length:M}).map(row => row = Array.from({length:N}).fill(0));

let coords = [];
input.forEach((item) => {
    item = item.split(' ').map(Number);
    let start = [item[1], item[0]];
    let end = [item[3]-1, item[2]-1];

    for(let i = start[0]; i <= end[0]; i++) {
        for(let j = start[1]; j <= end[1]; j++) {
            arr[i][j] = 1;
        }
    }
})

// [0, 0, 0, 0, 1, 1, 0],
// [0, 1, 0, 0, 1, 1, 0],
// [1, 1, 1, 1, 0, 0, 0],
// [1, 1, 1, 1, 0, 0, 0],
// [0, 1, 0, 0, 0, 0, 0];
// 맵 만들기

const visitedCoords = {};
function bfs(x, y) {
    const result = [];
    const queue = [[x,y]];
    const visited = {};
    visited[[x,y]] = true;
    visitedCoords[[x,y]] = true;
    let dx = [0, 0, 1, -1];
    let dy = [-1, 1, 0, 0];
    let cnt = 1;

    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 < arr.length &&
                    ny < arr[0].length ) &&
                // 좌표의 유효성 확인 
                    (arr[nx][ny] === 0) &&
                // 0일 경우에만 탐색 진행
                    (!visited[[nx,ny]])
                // visited 확인
                    )
                {   
                    visited[[nx,ny]] = true;
                    visitedCoords[[nx,ny]] = true;

                    cnt++;
                    queue.push([nx,ny]);
                }
            }
        }
    }
    return result;
}

let tmp = [];
for(let i=0; i<M; i++) {
    for(let j=0; j<N; j++) {
        if(arr[i][j] === 0 && !visitedCoords[[i,j]]) tmp.push(bfs(i,j).length)
    }
}
tmp.sort((a,b) => a-b)
let answer = tmp.length + '\n' + tmp.join(' ');
console.log(answer);

이번 문제를 풀면서,

• bfs 어느정도 익숙해졌다. bfs기본문제만 풀고 있는데, 이 문제 저번에 풀었던 단지번호 붙이기와 로직이 똑같다.
• 다만 map을 다시 만든다거나, 입출력이 바뀐다거나 했는데
• 이번 문제는 map이 문제였다. 어떻게 보면 쉬운 생각인데 절대 생각이 안나는 상하 반전 시키기를 떠올리기가 힘들었다..!
• 다만 bfs문제를 풀면서 함수를 조금 이쁘고, 보기 쉽게 하나 만들어 두면 두고두고 쓰기 좋지 않을까? 라는 생각이 들었다.
• 다음 문제는, 섬의 개수를 구하는 똑같은 유형의 dfs, bfs문제인데 bfs함수를 리팩토링해서 조금 더 쉽게 적용할 수 있도록 준비해야겠다.