[이것이 코딩테스트다] 5. DFS/BFS

[예제문제] 음료수 얼려먹기(DFS)

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

let input = require('fs').readFileSync('input.txt').toString().trim().split("\n");
let [n,m] =input.shift().split(" ").map(Number) ;  //m = 행의 갯수(y) , n = 열의 갯수(x) ;
let grid = input.map(x=>x.split(""));
let stack = []
let count = 0 ;

function finding(x, y){
    let dx = [-1,0,0,1] //좌우
    let dy = [0,-1,1,0] //위아래
    for (let i = 0 ; i < 4 ; i++ ){
        let xI  = x + dx[i] ;
        let yI  = y + dy[i] ;
        grid[y][x] = "2" ;
        if ((xI >= 0 ) && (yI >=0) && (yI < m) && (xI < n)){
            if (grid[yI][xI] === "0") stack.push([yI,xI]) ;
        }
    }
    if (stack.length != 0) {
        let [a, b] = stack.pop() ;
        finding(b, a)
    }
    return 1 ;
}

for (let i = 0 ; i < m ; i++){
    for (let j = 0 ; j < n ; j++ ){
        if ( grid[i][j] == "0" ) count += finding(j, i) ;
    }
}

console.log(count);

>> 탐색 예제문제와 동일하게 상하좌우로 움직여 탐색하도록 작성

>> DFS_stack(pop)을 이용하여 작성

 

---

 

[예제문제] 미로탈출(BFS)

현재 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

// 가는 곳 (1,1) => (0,0)  도달지 (n,m) => (n-1,m-1) ;
let queue = [[0,0,1]] ;
while (queue.length != 0 ){
    let [x, y, count] = queue.shift() ;
    if ((x === m-1)&&(y === n-1)) {
        console.log(count) ;
        break ;
    }
    else {
        let UD = [0,-1,1,0] ;  // [0] - left / [1] - up / [2] - down / [3] - right  
        let LR = [-1,0,0,1] ;
        for (let i = 0 ; i < 4 ; i++ ){
            let dx = x + LR[i] ;
            let dy = y + UD[i] ;
            input[y][x] = "2"
            if ((dx >= 0 ) && (dy >=0) && (dx < m) && (dy < n)){
                if (input[dy][dx] === "1" ) queue.push([dx,dy,count+1]) ;
            }
        }
    }
}

>> queue를 이용

>> 최소이동이기 때문에 BFS를 사용