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

otter·2022년 2월 6일
0

백준, 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이 추가로 들어가야하는 다른 좌표들로 바꿔주는 방식으로 구현했다.
profile
http://otter-log.world 로 이사했어요!

0개의 댓글