[C++][프로그래머스] 안전지대

프로그래머스

📄 문제

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

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

 

📝 풀이

#include <string>
#include <vector>
#include <cmath>
using namespace std;

vector<vector<bool>> ch;

int dx[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int dy[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };

int solution(vector<vector<int>> board) {
    
    int n = board.size();
    int answer = pow(n, 2);
    
    ch = vector<vector<bool>>(n, vector<bool>(n, false));
    
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            // 해당 위치가 지뢰라면?
            if(board[i][j] == 1)
            {
                --answer;
                ch[i][j] = true;
                
                for(int k = 0; k < 8; ++k)
                {
                    int ii = i + dy[k];
                    int jj = j + dx[k];
                    
                    if(ii < 0 || jj < 0 || ii >= n || jj >= n)
                        continue;
                    
                    if(ch[ii][jj])
                        continue;
                    
                    if(board[ii][jj] == 0)
                    {
                        --answer;
                        ch[ii][jj] = true;
                    }

                }
            }
        }
    }
    
    return answer;
}

• 2중 for문을 이용하여 지뢰가 있는 위치를 탐색합니다.
• 만약 지뢰가 있다면, 해당 위치로부터 8방향만큼 검사하여 안전 지역의 개수를 1씩 차감합니다.
• 만약, 8방향 위치에서 이미 검사하였거나, 지뢰가 있다면 넘어갑니다.