[백준 #1926] 그림 → BFS 활용

❓ 문제

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

🗝️ 입력

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

🗝️ 출력

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

🗝️ 예제 입력 및 출력

//입력
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

//출력
4
9

---

❗️ 비니's 풀이

BFS구현의 기본 정석 문제라는데 제대로 개념을 이해못한건지 코드로 구현하려니 x가 행인지, y가 행인지부터 헷갈려서 머리가 뽀개질것같다...

const fs = require("fs");
let input = fs
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((el) => el.split(" ").map((item) => +item));

//보드만들기
const [n, m] = input.shift();
//방문했는지 표시점 만들기
const visited = Array.from({ length: n }, () => new Array(m).fill(false));
//상하좌우 방향
let direction = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
];

let answer = 0; //그림의 개수
let result = []; //그림의 넓이

const BFS = (start) => {
    let queue = [start];
    let square = 0; //그림의 넓이
    while (queue.length) {
        let [y, x] = queue.shift();
        if (visited[y][x]) continue;
        visited[y][x] = true;
        square++;
        for (let i = 0; i < direction.length; i++) {
            let [dy, dx] = [y + direction[i][0], x + direction[i][1]]; //기준점을 기준으로 상하좌우 살피기
            if (dy < 0 || dx < 0 || dy >= n || dx >= m) continue; //보드판을 벗어나면 그냥 넘어가
            if (visited[dy][dx]) continue; //이미 방문한곳이면 그냥 넘어가
            if (input[dy][dx] === 1) {
                //보드판 내에 방문하지 않았는데 숫자1이야? 그럼 큐에 추가
                queue.push([dy, dx]);
            }
        }
    }
    if (square) {
        answer++;
        result.push(square);
    }
};

for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
        if (input[i][j] === 1 && !visited[i][j]) {
            //보드판 내에 방문하지 않은 곳이면 기준점에 들어가자
            BFS([i, j]);
        }
    }
}

if (!answer) return console.log(0 + "\n" + 0);
console.log(answer + "\n" + Math.max(...result));

---

⊕ Extra Knowledge ++

• Array.from()
  • 유사 배열 객체(array-like object)나 반복 가능한 객체(iterable object)를 얕게 복사해 새로운Array 객체를 만듭니다.

console.log(Array.from('foo'));
// Expected output: Array ["f", "o", "o"]

console.log(Array.from([1, 2, 3], x => x + x));
// Expected output: Array [2, 4, 6]

• "123" → +"123" → 123(number type)

Array.map((item) => +item)); //요소들을 number type으로 변환해줌