• [DFS] 음료수 얼려먹기 ( by using JavaScript )

    2021. 6. 2.

    by. KimBangg

    문제 

    N * M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0 이고 칸막이가 존재하는 부분은 1이다. 즉, 0으로 연결된 부분이 얼음 한 덩이가 얼려져 나오는 것이다. 구멍이 뚫려 있는 부분 끼리 상, 하, 좌, 우로 붙어 있는 경우가 서로 연결된 경우가 된다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

     

     

    예시

    예시로 아래와 같은 얼음판의 경우를 보자.

    00110
    00011
    11111
    00000

    출력 

    3

     

    How to Solve ?

     

    최초에 구멍이 뚫려있는 (=0) 을 만나면, DFS를 통해 0 주변(상,하,좌,우)에 모두 음료수를 붓는 방식으로 문제를 해결한다.

     

    즉, 0을 만나서 DFS를 수행 할 때 주변에도 0이 있다면 한번에 처리를 하여 1개의 아이스크림으로 간주한다.

     

    function DFS(x, y) {
    if (x <= -1 || x >= N || y <= -1 || y >= N) {
    return false;
    }
    if (iced[x][y] === 0) {
    iced[x][y] = 1;
    DFS(x - 1, y);
    DFS(x, y - 1);
    DFS(x + 1, y);
    DFS(x, y + 1);
    return true;
    }
    return false;
    }
    function solution() {
    let answer = 0;
    for (let i = 0; i < N; i++) {
    for (let j = 0; j < K; j++) {
    if (DFS(i, j) === true) {
    answer += 1;
    }
    }
    }
    return answer;
    }
    let [N, K] = [3, 3];
    const iced = [
    [0, 0, 1],
    [0, 1, 0],
    [1, 0, 1],
    ];
    console.log(solution());

    'PS > 기타' 카테고리의 다른 글

    댓글