[JavaScript/BFS] 백준 실버 1 : 1926번 - 그림

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

1926번: 그림

---

📌 작성한 코드 

// 1926
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, M] = input.shift().split(" ").map(Number);
const paper = input.map((item) => item.split(" ").map(Number));

const solution = () => {
    const dx = [1, -1, 0, 0];
    const dy = [0, 0, 1, -1];
    const visited = Array.from(Array(N), () => new Array(M).fill(false));

    const bfs = (a, b) => {
        const queue = [];
        queue.push([a, b]);
        visited[a][b] = true;

        let idx = 0;
        while (queue.length > idx) {
            const [x, y] = queue[idx++];
            for (let i = 0; i < 4; i++) {
                const nx = x + dx[i];
                const ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                    if (paper[nx][ny] === 1 && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        queue.push([nx, ny]);
                    }
                }
            }
        }

        return idx;
    };

    let count = 0;
    let max = 0;
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (paper[i][j] === 1 && !visited[i][j]) {
                const area = bfs(i, j);
                if (area > max) {
                    max = area;
                }
                count++;
            }
        }
    }
    console.log(count);
    console.log(max);
};

solution();

 

📌 풀이 

bfs 사용해서 그림의 크기와 개수를 구해서 출력해주기 

 

✅ 1. 방문여부 저장할 배열 선언 

const visited = Array.from(Array(N), () => new Array(M).fill(false));

 

✅ 2. bfs 작성 

- 큐에서 좌표를 꺼내서 해당 위치의 상하좌우를 살펴보면서 그림의 넓이를 구한다

-> idx를 사용해서 queue에 그림의 좌표가 들어갈때마다 증가시키면서 그림 칸의 넓이를 구해준다 

-> 또한 자바스크립트는 queue가 없어서 배열로 큐를 사용하다보니 shift()할 때 N의 시간 복잡도가 소요되어서, idx를 사용해서 idx를 이동하면서 shift()없이 해당 위치의 값을 꺼내올 수 있게 하였다.

 

- 다른 bfs를 작성할 때와 마찬가지로, 상하좌우의 좌표가 범위를 넘지 않고, 방문한적이 없고, 1이라서 그림인 경우에만 큐에 추가해준다.

- 그림의 넓이를 구하고 싶었던 것이니까 idx를 리턴해준다.

const bfs = (a, b) => {
        const queue = [];
        queue.push([a, b]);
        visited[a][b] = true;

        let idx = 0;
        while (queue.length > idx) {
            const [x, y] = queue[idx++];
            for (let i = 0; i < 4; i++) {
                const nx = x + dx[i];
                const ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                    if (paper[nx][ny] === 1 && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        queue.push([nx, ny]);
                    }
                }
            }
        }

        return idx;
    };

 

✅ 3. 반복문 돌면서 그림의 개수 구하기 

- 이중 루프를 돌면서 해당 위치에 방문하지 않았고, 1인 위치에서 bfs를 하며 각각의 그림 넓이를 구한다.

-> 구한 넓이 중 최댓값을 알고 싶은 것이니까 구할때마다 최댓값과 비교해서 업데이트 해준다.

- bfs를 한번 돌고 나면 그림 1개의 넓이를 확인한 것이니까 그림의 count를 증가시킨다.

let count = 0;
    let max = 0;
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (paper[i][j] === 1 && !visited[i][j]) {
                const area = bfs(i, j);
                if (area > max) {
                    max = area;
                }
                count++;
            }
        }
    }

 

---