백준, 2667 단지번호 붙이기 javascript

백준, 2667 단지번호 붙이기

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

👨‍💻 문제

문제 풀이

1. 이 문제에서 필요한 조건들
   - 시작점을 기준으로 4가지 좌표들을 탐색한다.

   • 4가지 좌표들은 다음과 같은 기준을 갖추어야 한다.
     • 4가지 좌표는 유효해야 한다. (0보다 커야하며, length보단 작아야 한다)
     • 4가지 좌표들은 좌표의 값이 1일때만 탐색해야 한다. (1이 아닐 경우 탐색하지 않는다.)
     • 이미 방문한 좌표는 탐색하지 않는다.

           for(let j = 0; j < 4; j++) {
                  let nx = X[0] + dx[j];
                  let ny = X[1] + dy[j];
                  if(( nx >= 0 &&
                      ny >= 0 &&
                      nx < arr.length &&
                      ny < arr.length ) &&
                  // 좌표의 유효성 확인 
                      (arr[nx][ny] === 1) &&
                  // 1일 경우에만 진행되므로 1인 경우만 좌표 출력
                      (!visited[[nx,ny]])
           // 함수로 만들어보는게 좋았을 것 같지만 문제를 풀땐 이런식으로 좌표의 유효성을 확인했다.

2. BFS의 기본 진행을 맞춘다.
   - BFS의 탐색을 진행해 queue와 visited객체를 선언한다.
   - 위의 조건들을 만족하는 좌표면 queue에 삽입한다.
   - vistied여부가 결정되면, cnt를 증가시킨다.

    function bfs(x, y) {
        const queue = [[x,y]];
        const visited = {};
        visited[[x,y]] = true;
        let dx = [0, 0, 1, -1];
        let dy = [-1, 1, 0, 0];
        let cnt = 1;
   
        while(queue.length) {
   
                for(let j = 0; j < 4; j++) {
                    let nx = X[0] + dx[j];
                    let ny = X[1] + dy[j];
                    if(( // 좌표의 유효성을 확인하는 부분
                        )
                    {   
                        visited[[nx,ny]] = true;
                        visitedCoords[[nx,ny]] = true;
                        cnt++;
                        queue.push([nx,ny]);
                    }
                }
            }
        }
        return cnt;
        }
   

3. 위의 방식으로 진행하면 queue의 push되는 한가지 값이 아니다.

   • queue에 있는 모든 값들에 대해서 진행해야 한다.

    for(let i=0; i<queue.length; i++) {
           let X = queue.shift();
           // queue에 있는 모든 값에 적용한다.
           
           // 좌표의 유효성을 확인하고 -1번
           // 유효한 좌표만 queue에 넣는다 - 3번
    }
   
   

💻 제출한 코드

const input = require('fs').readFileSync('example.txt').toString().trim().split('\n');
const N = input.shift();
const arr = input.map((item) => item.split('').map(Number))

function bfs(x, y) {
    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 X = queue.shift();
            for(let j = 0; j < 4; j++) {
                let nx = X[0] + dx[j];
                let ny = X[1] + dy[j];
                if(( nx >= 0 &&
                    ny >= 0 &&
                    nx < arr.length &&
                    ny < arr.length ) &&
                // 좌표의 유효성 확인 
                    (arr[nx][ny] === 1) &&
                // 1일 경우에만 진행되므로 1인 경우만 좌표 출력
                    (!visited[[nx,ny]])
                // visited 확인
                    )
                {   
                    visited[[nx,ny]] = true;
                    visitedCoords[[nx,ny]] = true;
                    cnt++;
                    queue.push([nx,ny]);
                }
            }
        }
    }
    return cnt;
}

// 정답 출력을 위해 좌표를 순회할때, 중복된 좌표를 순회하지 않기 위해서 추가로 삽입한 객체
// 여기서, ture로 지정된 좌표는 더이상 순회하지 않는다.
const visitedCoords = {};
const answer = [];
for(let i=0; i<N; i++) {
    for(let j=0; j<N; j++) {
        if(arr[i][j] === 1 && !visitedCoords[[i,j]]) answer.push(bfs(i,j));
    }
}

console.log(answer.length);
answer.sort((a,b) => a-b)
answer.forEach((item) => console.log(item));

이번 문제를 풀면서,

• 얼마전 DFS와 BFS의 자료구조를 공부하고 DFS와 BFS의 기본문제를 풀고 있다.
• 그치만, 나는 정말 자료구조를 벗어난 다른 문제를 어떻게 접근해야하는지 이해를 못하고 있었는데..
• 내가 배웠던 자료구조에서는 무조건 각 vertex들의 인접리스트를 객체 또는 배열로 받아야 했던 것이다. 😅
• 그래서 bfs와 dfs의 기본적은 이해는 하고 있었지만, 이를 코드로 구현하는 것은 쉽지 않았다.
• 기존에 공부했던 bfs코드는, queue에서 나온 값의 neighbor : 즉 인접리스트들을 확인하고 queue에 다시 push하는 로직이였는데 이 부분에서 착안했다.
• 그 neighbor이 추가로 들어가야하는 다른 좌표들로 바꿔주는 방식으로 구현했다.