백준 1926: 그림 - javascript(bfs)

문제 출처 

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

1926번: 그림

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

예제 입력 1 복사

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

예제 출력 1 복사

4
9

 

정답 풀이 코드 

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N,M] = input.shift().split(' ').map(Number);
const graph = input.map(v=> v.split(' ').map(Number));
const visited = [...Array(N)].map(()=> Array(M).fill(false)); 
const ds = [[0,1],[0,-1],[1,0],[-1,0]];
function bfs(i,j){
   const queue = [[i,j]]; 
    let area = 1; 
    while(queue.length){
      const [x, y] = queue.shift(); 
       for(let k=0; k<4; k++){
        const nx = x + ds[k][0];
        const ny = y + ds[k][1];
       if(nx<0|| ny<0 || nx>=N || ny> M) continue;     
       if(visited[nx][ny]) continue;     
       if(graph[nx][ny]){
            visited[nx][ny] = true; 
            area++; 
            queue.push([nx, ny]);
                }
              }
          }
    return area; 
}
let cnt = 0; 
let curArea = 0; 
let maxArea = 0; 
 for(let i=0; i<N; i++){
        for(let j=0; j<M; j++){
            if(graph[i][j] === 1 && !visited[i][j]){
                visited[i][j] = true; 
                cnt++;
              curArea = bfs(i,j);
             maxArea = Math.max(maxArea, curArea)
            }
        }
 }
console.log(cnt);
console.log(maxArea);

의사 코드 추가 

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N,M] = input.shift().split(' ').map(Number);
const graph = input.map(v=> v.split(' ').map(Number));
const visited = [...Array(N)].map(()=> Array(M).fill(false)); //방문한 위치는 true 값으로 변경해줄 것임 
const ds = [[0,1],[0,-1],[1,0],[-1,0]]; //사방면 확인하기 위함
function bfs(i,j){
   const queue = [[i,j]]; 
    let area = 1; //넓이 구하는 변수 
    while(queue.length){
      const [x, y] = queue.shift(); 
       for(let k=0; k<4; k++){//사방면 확인하는 반복문 
        const nx = x + ds[k][0];
        const ny = y + ds[k][1];
       if(nx<0|| ny<0 || nx>=N || ny> M) continue; //그래프를 벗어날 경우는 제낀다.     
       if(visited[nx][ny]) continue; //방문을 했었으면 제낀다.     
       if(graph[nx][ny]){ //1인 경우에만 queue에 push
            visited[nx][ny] = true;  //방문했다고 체크
            area++; //넓이 +1
            queue.push([nx, ny]);
                }
              }
          }
    return area; //최종 넓이 
}
let cnt = 0; //그림 개수  
let curArea = 0; //bfs를 통해 얻은 그림 넓이 
let maxArea = 0; //넓이 중 가장 큰 값 넣어줄 것임 
 for(let i=0; i<N; i++){
        for(let j=0; j<M; j++){
            if(graph[i][j] === 1 && !visited[i][j]){
                visited[i][j] = true; 
                cnt++;
              curArea = bfs(i,j);
             maxArea = Math.max(maxArea, curArea) // 큰 값을 maxArea에 넣어준다. 
            }
        }
 }
console.log(cnt);
console.log(maxArea);