[백준 1926번] BFS(너비 우선 탐색) - 그림 성공

✨ 문제 ✨

✨ 정답 ✨

const { count } = require("console");
const fs = require("fs");
const { nextTick } = require("process");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim();

// const fs = require('fs'); 
// let input = fs.readFileSync("/dev/stdin").toString().trim();



// 그림 개수, 그림 중 가장 넓이가 넓은 것의 넓이 출력
// 구해야 하는 것: 그림 개수, 그림 넓이들
// 그림이 없는 경우 가장 넓은 그림의 넓이는 0이다.
// 시간 초과를 방지하기 위해 1인 곳만 solution을 돌리기



// 두 번째 풀이
input = input.split('\n')

const [N, M] = input.shift().split(' ').map((el) => +el)
const array = input.map((el) => el.split(' ').map((el2) => +el2))

let pictureAreaArray = [];
let visited = Array.from({ length: N }, () => new Array(M).fill(false))
let dx = [0, 1, 0, -1]
let dy = [1, 0, -1, 0]

const solution = (startX, startY) => {
    let area = 0;   // 그림 넓이
    let queue = [[startX, startY]];

    while (queue.length) {
        let [currentX, currentY] = queue.shift();
        if (visited[currentX][currentY] === true) {
            continue;
        }
        visited[currentX][currentY] = true;
        area += 1;
        for (let i = 0; i < dx.length; i++) {
            for (let j = 0; j < dy.length; j++) {
                let nextX = currentX + dx[i];
                let nextY = currentY + dy[i]; 
                if (nextX >= 0 && nextY >= 0 && nextX < N &&nextY < M) {
                    if (visited[nextX][nextY] === true) {
                        continue
                    }
                    if (array[nextX][nextY] === 1) {
                        queue.push([nextX, nextY])
                    }
                } else {
                    continue
                }
            }
        }
    }
    if (area > 0) {
        pictureAreaArray.push(area)
    }
}

for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
        if (array[i][j] === 1 && visited[i][j] === false) {
            solution(i, j)
        }
    }
}

if (pictureAreaArray.length>0){
console.log(pictureAreaArray.length)
console.log(Math.max(...pictureAreaArray))
}else{
    console.log(0)
    console.log(0)
}




// 첫 번째 풀이

// input = input.split('\n')

// const [N, M] = input.shift().split(' ').map((el) => +el);
// input = input.map((el) => el.split(' ').map((el2) => +el2))
// let visited = Array.from({ length: N }, () => new Array(M).fill(false))
// let dx = [1, 0, -1, 0]
// let dy = [0, -1, 0, 1]

// let pCount = 0;   // 그림 개수
// let aCounts = []   // 그림 넓이 배열


// const solution = (startX, startY) => {
//     let aCount = 0;    // 그림 넓이
//     let queue = [[startX, startY]];

//     while (queue.length) {
//         let [currentX, currentY] = queue.shift();
//         if (visited[currentX][currentY] === true) {
//             continue;
//         }
//         visited[currentX][currentY] = true;
//         aCount++;
//         for (let i = 0; i < dx.length; i++) {
//             let nextX = currentX + dx[i];
//             let nextY = currentY + dy[i];
//             if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
//                 if (visited[nextX][nextY] === true) {
//                     continue;
//                 }
//                 if (input[nextX][nextY] === 1) {
//                     queue.push([nextX, nextY])
//                 }
//             } else {
//                 continue;
//             }
//         }
//     }
//     if (aCount > 0) {
//         pCount++;
//         aCounts.push(aCount);
//     }
// }

// for (let i = 0; i < N; i++) {
//     for (let j = 0; j < M; j++) {
//         if (input[i][j] === 1 && !visited[i][j]) {
//             solution(i, j)
//         }
//     }
// }

// if (pCount === 0) {
//     console.log(0)
//     console.log(0)
// } else if (pCount > 0 && aCounts.length > 0) {
//     console.log(pCount)
//     console.log(Math.max(...aCounts))
// }

🧵 참고한 정답지 🧵

💡💡 기억해야 할 점 💡💡

1. 처음에 풀 때는 그림의 개수(pCount)와 그림 넓이(aCounts)를 각각 구해서 두 개의 변수에 저장해야 한다고 생각했는데, 두 번째로 풀 때에는 그림 넓이 배열(pictureAreaArray)만 있으면 그림의 개수도 알 수 있으니 그림 개수를 세는 변수는 필요가 없다고 판단하여 변수를 하나만 사용하였다.