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

안전지대

문제 링크

안전지대

분석

지도에 대한 정보는 매개변수로 2차원 배열 board가 주어집니다.
해당 배열의 원소가 1일 경우 지뢰가 설치된 칸, 0일 경우 지뢰가 없는 칸입니다.

지도에서 지뢰가 매설된 칸 주변 8칸(상, 하, 좌, 우, 대각선)은 모두 위험지역으로 분류합니다.
이때, 지도에서 위험지역이 아닌 곳을 찾아 반환하는 문제입니다.

2차원 배열에서 지뢰가 위치하는 곳을 알기위해 배열 전체를 순회해야합니다.
이후, 찾은 지뢰를 기준으로 다음과 같은 방법이 있습니다.

1. 지도에 지뢰 주변을 위험으로 표시하고, 배열의 순회를 마친 후 안전한 위치를 탐색하는 방법이 있습니다.
2. 지도를 순회하며, 특정 위치를 기준으로 주변 8칸에 지뢰가 존재하는지 탐색하는 방법이 있습니다.

풀이

#include <vector>

using namespace std;

// 특정 위치를 기준으로 칸 주변을 탐색하기 위한 방향값
int directionX[9] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
int directionY[9] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};

int solution(vector<vector<int>> board) {
    int answer = 0;
    
    // Y축으로 지도를 순회하는 반복문
    for (int i = 0; i < board.size(); ++i)
    {
        // X축으로 지도를 순회하는 반복문
        for (int j = 0; j < board[i].size(); ++j)
        {
            // 현재 위치가 안전한지 상태를 저장하는 변수
            bool safe = true;
            
            // 현재 위치를 기준으로 주위에 지뢰가 존재하는지 확인한다.
            for (int k = 0; k < 9; ++k)
            {
                int dx = j + directionY[k];
                int dy = i + directionX[k];
                
                // 지도의 범위를 벗어났는지 확인
                if (dx >= 0 && dy >= 0 && dx < board[i].size() && dy < board.size())
                {
                    // 주위에 지뢰를 찾은 경우
                    if (board[dy][dx] == 1)
                    {
                        safe = false;
                        break;
                    }
                }
            }
            
            // 주변에 지뢰가 존재하지 않는다.
            if (safe)
            {
                answer += 1;
            }
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n^2)$입니다.

• 지도를 순회하는 반복문 $O(n^2)$
• 지도를 순회하며, 특정 위치가 안전한지 확인하는 반복문 $O(9) \approx O(1)$
• $O(n^2 \tiems O(1))$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

• 방향을 저장한 배열 directionX, directionY $O(9) \approx $O(1)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.15MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 3.63MB)
테스트 4 〉 통과 (0.01ms, 4.18MB)
테스트 5 〉 통과 (0.01ms, 4.22MB)
테스트 6 〉 통과 (0.01ms, 4.15MB)
테스트 7 〉 통과 (0.01ms, 4.22MB)
테스트 8 〉 통과 (0.01ms, 4.15MB)
테스트 9 〉 통과 (0.01ms, 4.25MB)
테스트 10 〉 통과 (0.01ms, 3.64MB)
테스트 11 〉 통과 (0.01ms, 4.22MB)
테스트 12 〉 통과 (0.01ms, 3.66MB)
테스트 13 〉 통과 (0.01ms, 4.14MB)
테스트 14 〉 통과 (0.01ms, 4.22MB)