[JS 백준] 2667.단지번호붙이기

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

2667번: 단지번호붙이기

BFS를 활용해 풀이한 문제다.

 

 

연결되어있는 단지의 길이와 갯수를 출력한다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';

const [n,...input] = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim().split('\n');


  const N = Number(n);
  const box = new Array(N);
  const dx = [1,0,-1,0];
  const dy = [0,1,0,-1];
  let result = [];

  for(let i = 0; i < N; i++){
      box[i] = new Array(N).fill(0);
      for(let j = 0;  j < N; j++){
          if(1===Number(input[i].charAt(j))){
              box[i][j] = true;
            }
        }
    }
    
    class Point{
        constructor(x,y){
            this.x = x;
            this.y = y;
        }
      }

      const BFS = (Pointt) =>{
        let count = 1;
        let queue = [];
        let x = undefined;
        let y = undefined;
        
        queue.push(Pointt);
        while(queue.length !== 0){
           const Points = queue.shift();
             x = Points.x;
             y = Points.y;
            for(let i = 0; i < 4; i++){
            let X = x+dx[i];
              let  Y = y+dy[i];
                if(X > -1 && X<N && Y > -1 && Y <N && box[X][Y] === true ){
                    queue.push(new Point(X,Y));
                    box[X][Y] = false;
                    count++;
                }
            }
        }
        return count;
      }

  for(let i = 0; i < N; i++){
    for(let j = 0; j < N; j++){
        if(box[i][j] === true){
            box[i][j] = false;
            result.push(BFS(new Point(i,j)))
        }
    }
  }

  
let ans = result.length;
 
console.log(ans + "\n" + `${result.sort((a,b)=> a-b).join("\n")}`)

 

배운것

 

1. 객체화

class 클래스명{
	constructor(매개변수1, 매개변수2){
    	this.매개변수1 = 매개변수1;
        this.매개변수2 = 매개변수2;
        }
}

constructor 함수를 사용해서 인자를 받고

클래스명.매개변수1 을 통해 값을 받아온다.

 

2. BFS flag 유의부분

 

계속해서 틀려서 원인을 찾지 못했다.

오류가 나는 테스트 케이스를 발견했다.

10
1010101010
0101010101
1010101010
0101010101
1010101010
0101010101
1010101010
0101010101
1010101010
0101010101

이 코드를 실행하면

1

1

1

1

1

1

이렇게 출력이 되어야하는데 0 0 0 0 0으로 출력이 됐다.

그 이유는 이러하다.

 const BFS = (Pointt) =>{
        let count = 0; // 문제부분1
        let queue = [];
        let x = undefined;
        let y = undefined;
        queue.push(Pointt);
        while(queue.length !== 0){
           const Points = queue.shift();
             x = Points.x;
             y = Points.y;
            for(let i = 0; i < 4; i++){
            let X = x+dx[i];
              let  Y = y+dy[i];
                if(X > -1 && X<N && Y > -1 && Y <N && box[X][Y] === true ){
                    queue.push(new Point(X,Y));
                    box[X][Y] = false; // 문제부분2
                    count++;
                }
            }
        }
        return count;
      }
      
     for(let i = 0; i < N; i++){
    for(let j = 0; j < N; j++){
        if(box[i][j] === true){
            result.push(BFS(new Point(i,j))) // 문제부분3
        }
    }
  }

 

단지의 길이가 하나일 경우 문제부분2에서 처음 단지의 부분을 flag true 처리해주지 못한다.

그렇다고 문제부분1에 count 초기값을 1로 하면 1의 오차가 발생한다.

그렇기에 문제부분3에서 BFS 함수에 들어오기 전 flag true 처리를 해주고 초기값을 1로 세팅해주면 해결이된다.

 

3. `${ }` 애용하자

console.log 는 시간이 많이 걸린다.

문자열을 출력할때는 += 으로 더하던가

join을 활용해 한번에 출력하자 

 

내일부터는 프로그래머스 JS 문제와 SQL 문제 하나씩 풀려고 노력해보자