프로그래머스 | 연결된 구역의 갯수

📌 문제

1과 0으로 이루어진 2차원 배열이 주어지면, 1로 연결되어 있는 부분을 찾아야 합니다. 상하좌우가 모두 0으로 이루어져 있다면, 분리되어 있는 곳으로 판단할 수 있습니다. 1로 이루어진 구역의 개수를 측정해서 반환해 주세요.

입출력 예

grid  = {
 [1, 1, 0, 0, 0],
 [1, 1, 0, 0, 0],
 [0, 0, 1, 0, 0],
 [0, 0, 0, 1, 1]
 }

예를 들어 위와 같은 배열이 주어진다면 1로 구분되는 3개의 구역이 존재하는 것으므로 3을 결괏값으로 반환합니다.

✨ 해결 방법

위 문제를 풀기 위해서는 DFS를 사용해야 합니다.

우선 위의 grid와 같은 형태를 가진 배열 visited를 선언하고 false로 가득 채워줍니다.
내부에 각 요소와 상하좌우를 각각 탐색하는 함수를 새로 만든 후, visited 내 grid와 같은 위치의 요소를 true로 만들어줍니다. 만약 이미 방문했거나 grid의 값이 0이거나, grid의 범위를 벗어난다면 그대로 함수를 종료하고, 그렇지 않을 경우에만 상하좌우를 같은 방법으로 탐색하도록 합니다.

영역의 갯수를 의미하는 변수 count를 선언한 후, 2중 for문을 통해 재귀방식으로 각 요소를 탐색합니다. 만약 grid 내 요소가 1이거나, 아직 방문하지 않았다면 dfs 함수를 실ㅇ행하고, count의 값을 증가시킵니다.

최종적으로 count 값을 반환합니다.

💻 solution

function solution(grid) {
    const rows = grid.length;
    const cols = grid[0].length;
    const visited = Array.from({ length: rows }, () => Array(cols).fill(0));

    // DFS 함수 정의
    function dfs(row, col) {
        if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] === "0" || visited[row][col]) {
            return 0;
        }

        visited[row][col] = 1;

        dfs(row - 1, col);
        dfs(row + 1, col);
        dfs(row, col - 1);
        dfs(row, col + 1);
    }

    let count = 0;

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === "1" && !visited[i][j]) {
                dfs(i,j);
                count ++;
            }
        }
    }

    return count;
}