[코딩테스트 javascript] 안전지대 - DFS , BFS, 그래프 탐색 알고리즘

안전지대

https://school.programmers.co.kr/learn/courses/30/lessons/120866

프로그래머스

문제 설명

다음 그림과 같이 지뢰가 있는 지역과 지뢰에 인접한 위, 아래, 좌, 우 대각선 칸을 모두 위험지역으로 분류합니다.

지뢰는 2차원 배열 board에 1로 표시되어 있고 board에는 지뢰가 매설 된 지역 1과, 지뢰가 없는 지역 0만 존재합니다.
지뢰가 매설된 지역의 지도 board가 매개변수로 주어질 때, 안전한 지역의 칸 수를 return하도록 solution 함수를 완성해주세요.

 

 

문제 풀이 

 

이 문제는 DFS를 이용하여 간단하게 생각하면 된다.

처음에 구현(시뮬레이션) 문제인줄 알고 여러 시도를 해보고 시간 소비를 많이 했다.

 

1. 방향 설정

위 사진 처럼 y (arr의 인덱스) x(arr의 요소의 index)의 방향을 설정해준다.

//방향
    const dx = [-1,0,1,-1,1,-1,-0,1]
    const dy = [-1,-1,-1,0,0,1,1,1 ]

 

2. 이중 for문 

board(입력값)의 길이 만큼 for문 돌리기

for (let y=0; y<n ; y++) {
        for(let x=0;x<n;x++) {
        }
}

 

3. 지뢰 찾기 - DFS, BFS

board[y][x]가 0이면서 모든 방향에 지뢰가 없는 경우를 골라서  safe에 저장한다.

한 노드에서 인접한 모든 노드를 검색하는 알고리즘 즉, DFS/BFS 를 이용하여 문제를 풀었다.

   if (board[y][x] === 0  ) {
               let 지뢰 = 0;
               for(let i =0; i<8; i++) {
                   // 모든 방향 체크
                    let ny = y + dy[i]
                    let nx = x + dx[i]
                    
                    if ( (0 <= ny && ny < n ) && (0 <= nx && nx <n) ) {  
                        if (board[ny][nx] === 1 ) {
                             지뢰++;   
                        }
                    }
                   // 모두 확인했을때 1이 없다면
                   if (i===7 && 지뢰 === 0 ) safe++;
                }
            }

 

 

안전지대 완성코드

//그래프 탐색 문제 (BFS/DFS)

function solution(board) {
    let safe = 0;
    let n = board.length;    
    
    //방향
    const dx = [-1,0,1,-1,1,-1,-0,1]
    const dy = [-1,-1,-1,0,0,1,1,1 ]
    
    //for문 - dfs 
    for (let y=0; y<n ; y++) {
        for(let x=0;x<n;x++) {
            if (board[y][x] === 0  ) {
               let 지뢰 = 0;
               for(let i =0; i<8; i++) {
                   // 모든 방향 체크
                    let ny = y + dy[i]
                    let nx = x + dx[i]
                    
                    if ( (0 <= ny && ny < n ) && (0 <= nx && nx <n) ) {  
                        if (board[ny][nx] === 1 ) {
                             지뢰++;   
                        }
                    }
                   // 모두 확인했을때 1이 없다면
                   if (i===7 && 지뢰 === 0 ) safe++;
                }
            }            
        }
    }        
    return safe;
}