문제

풀이

그래프를 탐색해서 구하는 전형적인 DFS, BFS 문제이다.
최단 거리를 구하는거가 아니고 모든 경우의 수를 탐색해서 구하는 문제 이기 때문에 DFS를 사용해서 문제를 풀었다.

이차원 배열을 (0,0) 부터 (n-1,n-1) 지점까지 모두 돌면서 각 지점이 1인지를 판단하고 각 지점에서 DFS를 돌면서 근처에 있는 모든 1 지점의 수를 1씩 더해서 DFS가 모두 끝나면 그 값을 전체 배열값에 넣는식으로 풀이를 생각했다.

그 후 최종 배열을 정렬하고 그 개수를 출력해주면 된다.

코드

// 입력 받기
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().split("\n");

// 답에 필요한 변수들 선언
let answer = [];
let n = +input[0];
let graph = [];
let home = 0;

// 입력값을 보기좋게 숫자로 변환해서 graph 배열에 대입
for (let i = 1; i < n + 1; i++) {
    let a = [];
    for (let j = 0; j < n; j++) {
        a.push(+input[i][j])
    }
    graph.push(a);
}

// 처음부터 끝까지 돌면서 1인 지점에서 DFS시작
for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        if (graph[i][j] === 1) {
            home = 0;
            graph[i][j] = 0;
            DFS(i, j);
            answer.push(home);
        }
    }
}

// DFS 함수
function DFS(x, y) {
    home += 1;
    let dx = [0, 1, 0, -1];
    let dy = [1, 0, -1, 0];
    for (let h = 0; h < 4; h++) {
        let nx = x + dx[h];
        let ny = y + dy[h];
        if (nx >= 0 && ny >= 0 && nx < n && ny < n && graph[nx][ny] === 1) {
            graph[nx][ny] = 0;
            DFS(nx, ny);
        }
    }

}

// 값 출력
answer.sort((a, b) => a - b);
console.log(answer.length);
for (let i = 0; i < answer.length; i++) {
    console.log(answer[i]);
}