백준 2667

https://www.acmicpc.net/problem/2667 단지번호 붙이기 문제이다.

다음은 내가 예제대로 푼 내용이다.

우선 입력받은 값을 배열로 만들어주었다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\r\n');


[arraySize,...elements] = input;
arraySize = Number(arraySize);
const map = [];

for(let i = 0; i<arraySize; i++){
    let innerArr = [];
    for(let j = 0; j<arraySize; j++){
        innerArr.push(Number(elements[i][j]))
    }
    map.push(innerArr);
}

map = [
[0, 1, 1, 0, 1, 0, 0],
[0, 1, 1, 0, 1, 0, 1],
[1, 1, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 1, 1, 1],
[0, 1, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 0, 0, 0]
]

map[0][0] ~ map[6][6] 까지 총 49개의 정점이 있는 셈이다.
이중 for문을 돌면서 map안에 있는 각각의 정점들을 탐색한다.
각 정점에 대해서 다음을 수행한다.

그림으로 표현하면 이런 식이다.

다음은 필요한 준비물이다.

1. BFS에 사용될 큐이다.

   class Node{
      constructor(data){
          this.data = data;
          this.link = null;
      }
   }
   class ListQueue {
      constructor(){
          this.front=null;
          this.rear=null;
          this.size = 0;
      }
      isEmpty(){
          if(this.front === null){
              return 1;
          } else {return 0;}
      }
      enQueue(data){
          let newNode = new Node(data);
          if(this.isEmpty()===1){
              this.front = newNode;
              this.rear = newNode;
          } else {
              this.rear.link = newNode;
              this.rear = newNode;
          }
          this.size = this.size+1;
      }
      deQueue(){
          if(this.isEmpty()===1){
             return -1;
          } else {
              this.size = this.size - 1;
              let deQueueData = this.front.data;
              this.front = this.front.link;       
              if(this.front === null){
                  this.rear = null;
              }
              return deQueueData;
          }
      }
   }

2. 정점의 방문 여부를 표현한 visited 배열이다.
   방문한 정점 = true, 방문하지 않은 정점 = false.
   물론 map과 같은 크기를 갖는다.

const visited = [];
for(let i = 0; i<arraySize; i++){
    let arr = [];
    for(let j = 0; j<arraySize; j++){
        arr.push(false);
    }
    visited.push(arr);
}   

순서도 상에 있는 사각형안에 있는 두 과정은
각각 함수로 분리해주었다.

먼저 한 정점에 대해서 이웃한 정점을 찾는 함수이다.

const getAdjacentVertexex = (i,j)=>{
    let adjacentVertex;
    let leftSideVertex;
    let rightSideVertex;
    let upperSideVertex;
    let downSizeVertex;
    if(i === 0 || j===0){
        if(i===0 && j!==0){
               leftSideVertex = [i,j-1];
               downSizeVertex = [i+1,j];
               rightSideVertex = [i,j+1];            
        }
        else if(i!==0 && j===0){
               upperSideVertex =[i-1,j];
               downSizeVertex = [i+1,j];
               rightSideVertex = [i,j+1];            
        }
        else{
            downSizeVertex = [i+1,j];
            rightSideVertex = [i,j+1];            
        }
    }

    else if(i===arraySize-1 || j===arraySize-1){
        if(i===arraySize-1 && j!==arraySize-1){
            leftSideVertex = [i,j-1];
            upperSideVertex =[i-1,j];
            rightSideVertex = [i,j+1]; 
        }

        else if(i!==arraySize-1 && j===arraySize-1){
            leftSideVertex = [i,j-1];
            downSizeVertex = [i+1,j];
            upperSideVertex =[i-1,j];
        }
        else{
            leftSideVertex = [i,j-1];
            upperSideVertex =[i-1,j];
        }
    }
    else{
        leftSideVertex = [i,j-1];
        upperSideVertex =[i-1,j];
        rightSideVertex = [i,j+1]; 
        downSizeVertex = [i+1,j];
    }
          adjacentVertex = [upperSideVertex,leftSideVertex,downSizeVertex,rightSideVertex];
          return adjacentVertex;
        }

설명은 생략한다.

다음은 이웃한 정점들을 방문하고 큐에 넣는 함수이다.

 const visitAdjacentVertexex = (adjacentVertex)=>{
          adjacentVertex.forEach((v)=>{
            if(v!==undefined){
                if(map[v[0]][v[1]]!==0){ // 인접한 정점을 방문
                    numOfVertexPerSet++;
                    visited[v[0]][v[1]] = true;
                    lq.enQueue([v[0],v[1]]);
                    map[v[0]][v[1]] = 0;
                     //값이 1인 인접한 정점을 방문하고 q에 넣음
                }   
            }
        })
        return numOfVertexPerSet;
      }

다음은 전체 코드이다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\r\n');


[arraySize,...elements] = input;
arraySize = Number(arraySize);
const map = [];

for(let i = 0; i<arraySize; i++){
    let innerArr = [];
    for(let j = 0; j<arraySize; j++){
        innerArr.push(Number(elements[i][j]))
    }
    map.push(innerArr);
}

class Node{
    constructor(data){
        this.data = data;
        this.link = null;
    }
}

class ListQueue {

    constructor(){
        this.front=null;
        this.rear=null;
        this.size = 0;
    }

    isEmpty(){
        if(this.front === null){
            return 1;
        } else {return 0;}

    }

    enQueue(data){
        let newNode = new Node(data);
        if(this.isEmpty()===1){
            this.front = newNode;
            this.rear = newNode;
        } else {
            this.rear.link = newNode;
            this.rear = newNode;
        }
        this.size = this.size+1;
    }

    deQueue(){
        if(this.isEmpty()===1){
           return -1;
        } else {
            this.size = this.size - 1;
            let deQueueData = this.front.data;
            this.front = this.front.link;
            
            if(this.front === null){
                this.rear = null;
            }
            return deQueueData;
        }
    }
}

const visited = [];
for(let i = 0; i<arraySize; i++){
    let arr = [];
    for(let j = 0; j<arraySize; j++){
        arr.push(false);
    }
    visited.push(arr);
}

const lq = new ListQueue();
const getAdjacentVertexex = (i,j)=>{
    let adjacentVertex;
    let leftSideVertex;
    let rightSideVertex;
    let upperSideVertex;
    let downSizeVertex;
    if(i === 0 || j===0){
        if(i===0 && j!==0){
               leftSideVertex = [i,j-1];
               downSizeVertex = [i+1,j];
               rightSideVertex = [i,j+1];            
        }
        else if(i!==0 && j===0){
               upperSideVertex =[i-1,j];
               downSizeVertex = [i+1,j];
               rightSideVertex = [i,j+1];            
        }
        else{
            downSizeVertex = [i+1,j];
            rightSideVertex = [i,j+1];            
        }
    }

    else if(i===arraySize-1 || j===arraySize-1){
        if(i===arraySize-1 && j!==arraySize-1){
            leftSideVertex = [i,j-1];
            upperSideVertex =[i-1,j];
            rightSideVertex = [i,j+1]; 
        }

        else if(i!==arraySize-1 && j===arraySize-1){
            leftSideVertex = [i,j-1];
            downSizeVertex = [i+1,j];
            upperSideVertex =[i-1,j];
        }
        else{
            leftSideVertex = [i,j-1];
            upperSideVertex =[i-1,j];
        }
    }
    else{
        leftSideVertex = [i,j-1];
        upperSideVertex =[i-1,j];
        rightSideVertex = [i,j+1]; 
        downSizeVertex = [i+1,j];
    }
          adjacentVertex = [upperSideVertex,leftSideVertex,downSizeVertex,rightSideVertex];
          return adjacentVertex;
        }

      const visitAdjacentVertexex = (adjacentVertex)=>{
          adjacentVertex.forEach((v)=>{
            if(v!==undefined){
                if(map[v[0]][v[1]]!==0){ // 인접한 정점을 방문
                    numOfVertexPerSet++;
                    visited[v[0]][v[1]] = true;
                    lq.enQueue([v[0],v[1]]);
                    map[v[0]][v[1]] = 0;
                     //값이 1인 인접한 정점을 방문하고 q에 넣음
                }   
            }
        })
        return numOfVertexPerSet;
      }

let numOfSet = 0; // 정점끼리 연결되어 있는 집합의 갯수
let numOfVertexPerSet = 0;
let answer_numOfVertexPerSet= [];

const bfs = (map)=>{
    for(let i = 0; i<arraySize; i++){
        for(let j = 0; j<arraySize; j++){

            let targetVertex = map[i][j];
            if(targetVertex===0){   // 해당 점점이 0이면 다음 해당 정점에 대해 작업을 수행하지 않고 다음 정점으로 넘어감
                continue;
            }
            
            numOfVertexPerSet = 0;
            visited[i][j]= true; // 해당 정점이 1이면 해당 점점을 방문
            let arr= [i,j];
            lq.enQueue(arr) // 방문한 정점을 Q에 넣음.
            map[i][j] = 0; // 방문했으면 0으로 바꿈
            numOfSet++; 
            numOfVertexPerSet++;
            while(lq.isEmpty()===0){
                 let poppedVertex = lq.deQueue();
                 visitAdjacentVertexex(getAdjacentVertexex(poppedVertex[0],poppedVertex[1]));
                 //해당 정점이 1일경우 인접한 정점을 구함
                 //인접한 정점을 모두 살펴본 상태
            }
            answer_numOfVertexPerSet.push(numOfVertexPerSet);
            // console.log(numOfVertexPerSet);
            }
        }
    }
    
    bfs(map);

    numOfSet = numOfSet +"";
    console.log(numOfSet);
    answer_numOfVertexPerSet.sort((a,b)=>a-b);
    console.log(answer_numOfVertexPerSet.join('\n'));

이렇게 열심히 풀었지만 결과적으로 틀렸다 ㅜㅜ..
자꾸 런타임 에러(Type Error)가 떴다.