[Programmers] #120866 - 안전지대 [Java][C++][Python]

문제 링크

---

1. 아이디어

주어진 board에서 안전지대의 칸 수를 구하는 문제로 지뢰가 있는 칸과 이웃한 8방향이 위험지대다. 방문 배열을 둬서 지뢰를 발견하면 해당 칸 및 이웃한 칸까지 위험지대로 체크하는 과정을 모든 지뢰에 대해 수행한 후 안전지대의 크기를 셌다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N^2)$	$O(N^2)$

($N$ = board 한 변의 길이)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {

    static int[] dr = {-1, -1, -1, 0, 1, 1, 1, 0};
    static int[] dc = {-1, 0, 1, 1, 1, 0, -1, -1};

    public int solution(int[][] board) {
        int n = board.length;
        boolean[][] vis = new boolean[n][n];

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (board[r][c] == 1) {
                    vis[r][c] = true;
                    for (int d = 0; d < 8; d++) {
                        int nr = r + dr[d];
                        int nc = c + dc[d];

                        if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
                        vis[nr][nc] = true;
                    }
                }
            }
        }

        int cnt = 0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (!vis[r][c]) cnt++;
            }
        }

        return cnt;
    }
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100;
bool vis[MAXN][MAXN];
int dr[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dc[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

int solution(vector<vector<int>> board) {
    int n = board.size();

    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (board[r][c]) {
                vis[r][c] = true;
                for (int d = 0; d < 8; d++) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];

                    if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
                    vis[nr][nc] = true;
                }
            }
        }
    }

    int cnt = 0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (!vis[r][c]) cnt++;
        }
    }

    return cnt;
}

def solution(board):
    n = len(board)
    vis = [[False] * n for _ in range(n)]

    for r in range(n):
        for c in range(n):
            if board[r][c]:
                vis[r][c] = True
                for dr, dc in ((-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n:
                        vis[nr][nc] = True

    return sum(row.count(False) for row in vis)

---