백준 2667 단지번호붙이기

하다보면 되는구나 를 느꼈고
DFS / BFS 두가지 방법으로 풀어봤어요
어젯 밤 새벽까지 과제를 하다가 문제를 풀지 못해
오늘 오전부터 후딱 풀어 본 문제
모두 스터디원들의 추천문제였고 내게 중요했던건 말씀해진 풀이를 최대한 잊는것
잊으려고 어제 수엄 끝나고 낮잠(?) 자고
아이언맨3보고 과제만 했더니 다까먹어서 힘들게 풀었읍니다

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

문제를 천천히 보며 이해하자

• 주어진 단지 모양의 매트릭스는 N x N 으로 이루어진 정사각형이다
• 0과 1로 이루어져 있으며 0은 의미가 없고 1은 단지를 구성하는 집을 나타낸다
• 우리가 찾아야 하는 답은 단지의 갯수, 각 단지를 이루는 집의 갯수 를 오름차순으로 보여주는 것이다
• 해당 문제처럼 인접행렬 (매트릭스) 문제를 풀 때에는 방문 배열을 같은 모양으로 초기화 해 주는것이 좋아보인다
• 첫번째로 모든 집에 방문하는 것을 목표로 하였다
• 동작을 눈으로 확인하여 방문되는 시점에 맞춰 적절히 카운트를 주었다
• 나는 문제를 풀때 큰 틀을 먼저 잡아놓고 세세한 부분을 교정해주며 구현하는 편이다

//BFS 풀이

const fs = require('fs');
const input = fs.readFileSync('example.txt').toString().trim().split('\n')
// const input = fs.readFileSync('dev/stdin', 'utf-8').toString().trim().split('\n')

const N = input.shift()

const visited = Array.from({length : N},()=>Array.from({length : N}, ()=>false))

let count = 0
let numbering = 0
let numberingsArr = []

const bfs = (r, c) => {
    const queue = []
    visited[r][c] = true
    queue.push([r, c])
    numbering++
  //bfs가 한번 시작할때 첫번째 집을 탐색하며 들어온다.
    while(queue.length != 0){
        const Dir = [[-1,0],[1,0],[0,-1],[0,1]]
        const [cur_r, cur_c] = queue.shift()
        for(let i=0; i<4; i++){
            const next_r = cur_r - Dir[i][0]        //상 하 컨트롤은 row로 한다
            const next_c = cur_c - Dir[i][1]        //좌 우 컨트롤은 col으로 한다
            if( next_r < N &&
                next_c < N &&
                next_r >= 0 &&
                next_c >= 0 &&
                visited[next_r][next_c] == false &&
                input[next_r][next_c] == '1'){
                    queue.push([next_r, next_c])
                    visited[next_r][next_c] = true
                    numbering++
               //이 곳에서 numbering을 하나 씩 더해주면 첫번째 집 이후에 한 단지가 몇 개의 집으로 이루어져 있는지 확인할 수 있다
                }

        }
    }
}
for(let i=0; i<N; i++){
    for(let j=0; j<N; j++){
        if(visited[i][j] == false && input[i][j] == '1'){
            bfs(i, j)
            count++
          //한번의 단지를 모두 확인하고 bfs를 빠져나온 후 단지 개수를 하나 늘려준다
            numberingsArr.push(numbering)
          //위 bfs함수 내에서 구한 집의 개수를 한 배열로 모아주기 위해 푸쉬해준다
            numbering = 0
          //다음 사이클에서 새로운 단지의 개수를 구하기 위하여 0으로 초기화 해준다

        }
    }
}

console.log(`${+count}\n${numberingsArr.sort((a,b)=>{return a - b}).map(Number).join('\n')}`)

//DFS 풀이
const fs = require('fs');
const input = fs.readFileSync('example.txt').toString().trim().split('\n')
// const input = fs.readFileSync('dev/stdin', 'utf-8').toString().trim().split('\n')

const dfs = (r, c) => {
    visited[r][c] = true
    numbering++
  /*
  bfs와 다르게 dfs는 자기 자신을 재귀적으로 호출하므로 함수 상단에서
  집의 숫자를 세어주면 한 단지를 모두 탐색하며 우리가 원하는 값을 얻어낼 수 있다
  */
    let [cur_r, cur_c] = [r, c]
    const Dirs = [[-1, 0],[1, 0],[0, -1],[0, 1]]
    for(const dir of Dirs){
        const next_r = cur_r + dir[0]
        const next_c = cur_c + dir[1]
        // const [next_r, next_c] = [cur_c + dir[0], cur_c + dir[1]]
        if( next_r >= 0 &&
            next_c >= 0 &&
            next_r < N &&
            next_c < N &&
            visited[next_r][next_c] == false &&
            input[next_r][next_c] == '1'){
            dfs(next_r,next_c)
        }
    }
}

for(let i=0; i<N; i++){
    for(let j=0; j<N; j++){
        if(visited[i][j] == false && input[i][j] == '1'){
        dfs(i, j)
        count++
        numberingsArr.push(numbering)
        numbering=0
        //이 부분은 bfs와 동일하다 한 단지를 탐색 후 빠져나오는 것은 동일하기 때문이다.
        }
    }
}

console.log(`${+count}\n${numberingsArr.sort((a,b)=>{return a - b}).map(Number).join('\n')}`)