최근에 나온 문제라 풀이가 많이 없는.. 구글링해도 나오지 않는 문제이기에
나의 글이 누군가에게 도움이 됐으면 하는 작은 바람을 담아 얼른 글을 작성해본다..

---

📍 문제

[프로그래머스] Lv.0 안전지대

📍 풀이

• 처음에.. Lv.0이라서 그냥 단순 무식하게 모두 조건문으로 풀면 풀릴 줄 알았다 ㅎㅎ;
  내가 생각한 알고리즘은.. 코드를 보면 확인할 수 있다 😭

💻 첫번째 풀이 (오답)

import numpy as np

def solution(board):
    n = len(board)
    danger = [[0 for _ in range(n)] for _ in range(n)]
    answer = 0
    for i in range(n):
        for j in range(n):
            if board[i][j] == 1:
                if j == 0: # 맨 위에 붙어 있는 경우
                    if i == 0: # 맨 위에 붙어있으면서 맨 왼쪽에 있을 경우
                        danger[i+1][j] = 1
                        danger[i][j+1] = 1
                        danger[i+1][j+1] = 1
                    elif i == n-1: # 맨 위에 붙어있으면서 맨 오른쪽에 있을 경우
                        danger[i-1][j] = 1
                        danger[i-1][j+1] = 1
                        danger[i][j+1] = 1
                    else: # 맨 위에 붙어있지만 가생이에 있지 않은 경우
                        for x in range(i-1, i+2):
                            for y in range(j, j+2):
                                danger[x][y] = 1
                elif j == n-1: # 맨 아래 붙어 있는 경우
                    if i == 0: # 맨 아래에 붙어있으면서 맨 왼쪽에 있을 경우
                        danger[i][j-1] = 1
                        danger[i+1][j+1] = 1
                        danger[i+1][j] = 1
                    elif i == n-1: # 맨 아래에 붙어있으면서 맨 오른쪽에 있을 경우
                        danger[i-1][j-1] = 1
                        danger[i][j-1] = 1
                        danger[i-1][j] = 1
                    else:
                        for x in range(i-1, i+2):
                            for y in range(j-1, j+1):
                                danger[x][y] = 1
                else: # 중간 어느곳에 있는 경우
                    for x in range(i-1, i+2):
                        for y in range(j-1, j+2):
                            try:
                                danger[x][y] = 1 
                            except:
                                pass
    
    danger_np = np.array(danger)
    answer = n*n - danger_np.sum()
    return answer

주석에 적혀있다시피 모든 경우의 수를 if문으로 나눠주려고 했다.
근데 이러면 오류가 나고 당연히 채점이 안됨..
스터디에 나온 문제라 어떻게든 시간안에 풀어보려고 조건문을 일단 줄줄이 썼지만..(46줄짜리 코드) 문제에서 원하는 바는 이게 아닐 것이라고 생각해요🤔
스터디가 끝난 후에도 계속 이 방법대로 풀려고 하다가! 포기함..

💻 두번째 풀이 (정답)

스터디조원이 패딩(Padding)과 collections모듈의 Counter클래스를 이용하면 된다는 힌트를 줬다.
따라서 numpy와 Counter를 import해주면 된다.

Numpy를 이용하여 패딩하기 - np.pad()

패딩이라 하면 대충 배열 테두리를 감싸주는 작업을 한다고 생각하면 된다.
영상처리에서는 이미지에 함수를 적용하려면.. 모서리 값을 처리하기 위해 패딩을 한다. (배열에 없는 값에 함수를 적용할 순 없으니까!)
마찬가지로 2차원 배열을 다루는 경우 모서리나 최상단, 최하단 값을 처리해주려면 패딩을 하면 되겠구나! 를 깨달은 문제였다.

import numpy as np
np.pad(array,
        pad_width=((a, b), (c, d)),
        mode='constant',
        constant_values=0
        )

• array: 패딩을 할 배열
• pad_width: 테두리를 몇 줄 만들 지 지정 (a: 위쪽 행, b: 아래쪽 행, c: 왼쪽 열, d: 오른쪽 열)
• mode: pad method를 적용하는 모드를 지정함 (기본값은 constant)
  • constant: 특정한 값으로 테두리를 추가
  • edge: 원본 배열에서 가장 가까운 모서리에 있는 값으로 테두리 추가
  • maximum: 특정 테두리 위치에 존재하는 값에서 행/열에 있는 최대값으로 테두리 추가
• constant_values: 테두리에 채워 넣을 상수값 (기본값은 0)

일단 이렇게 패딩을 해주면 try-except를 해줄 필요도 없다.

Counter클래스는 우리에게 안전한 구역인 0의 개수를 세줄 필요가 있기에 사용했다.

코드

import numpy as np
from collections import Counter

def solution(board):
    n = len(board)
    # pad() 함수를 사용해 주어진 2차원 배열의 상하좌우 1줄씩 -1을 추가한 board_padded 생성
    board_padded = np.pad(board, ((1, 1), (1, 1)), constant_values = -1)
    danger_array = np.pad(board, ((1, 1), (1, 1)), constant_values = -1)
    for i in range(1, n+1):
        for j in range(1, n+1):
            if board_padded[i][j] == 1:
                for x in range(i-1, i+2):
                    for y in range(j-1, j+2):
                        danger_array[x][y] = 1
    danger_list = danger_array.reshape(1, -1).squeeze()
    answer = Counter(danger_list)[0]
    # 결과 값 반환
    return answer

• board_padded = np.pad(board, ((1, 1), (1, 1)), constant_values = -1): 상, 하, 좌, 우 1개의 테두리를 추가한다는 뜻이고 그 때 그 테두리 값은 -1로 지정한다.
  
  다음과 같이 패딩된 것을 확인할 수 있다.
  문제에서 폭탄 주변 인근 8개만 위험구역이므로, 상하좌우로 1줄 씩만 추가해주면 된다.
• 이후 똑같은 danger_array를 생성해준다. board_padded만 이용할 경우 1이 연속으로 연결되어 있는 경우 값을 처리하기가 곤란해진다. 이유가 뭐냐면 board_padded[i][j] == 1이라는 조건을 사용하기 때문에 인근 값을 1로 바꾸면 나중에 폭탄이 없던 자리였음에도 이 조건 때문에 그 근처도 위험지역으로 분리되고, 뭐 다른 상수 100같은걸 넣게 되면 폭탄이 실제로 있는 자리도 100으로 바꾸기 때문에 위험지역을 제대로 출력하지 않는다. (1인 자리가 더이상 1이 아니라서 폭탄이 있다고 판단할 수 X)
  따라서 나는 배열을 하나 더 선언해줬고! 거기서 1로 바꿔주는 작업을 진행했다.
• for문이 1부터 시작하는 이유는 0번 인덱스같은 경우 어차피 패딩된 자리이기 때문에 확인해 줄 필요가 없다.
• board_padded[i][j] == 1 이면 danger_array의 똑같은 자리에도 1로 만들어준 다음 0의 개수만 세서 답을 출력해주면 끝

훨씬 간결하고 보기좋은 풀이!

📍 다른사람 풀이

💻 BFS 사용

from collections import deque

def solution(board):
    dx = [-1, 1, 0 , 0, 1, 1, -1, -1]
    dy = [0, 0, -1, 1, -1, 1, 1, -1]
    length = len(board)
    visited = [[False] * length for _ in range(length)]

    def bfs(x, y):
        dq = deque()
        dq.append((x, y))
        while dq:
            a, b = dq.popleft()
            visited[a][b] = True
            for i in range(8):
                nx = dx[i] + a
                ny = dy[i] + b
                #위험지역으로 둬야함 
                if 0<=nx<length and 0<=ny<length and not visited[nx][ny]:
                    if board[nx][ny] == 1:
                        dq.append((nx, ny))
                    else:
                        board[nx][ny] = 2 #위험지역 처리 

    for i in range(length):
        for j in range(length):
            if board[i][j] == 1:
                bfs(i, j)
    result = 0
    for i in range(length):
        result += board[i].count(0)
    return result

이런 주변지역 탐색 문제를 볼 때 마다 BFS나 DFS를 사용하면 되겠다.. 라고 생각은 하지만.. 자꾸 그냥 쉽게 그냥 구현할 수 있는 방법을 찾게 되는 것 같다. 사고를 더 깊게 안하게 된달까나.. 😭

💻 초간결 코드

import numpy as np
def solution(board):
    board = np.array(board)
    for a, b in zip(*np.where(board == 1)):
        board[a-1 if a else 0:a+2, b-1 if b else 0:b+2] = 1
    return len(board[board == 0])

이 코드에 대한 해설은 나중에 달도록 하겠다.. (지금 너무 피곤해요 죄송함니다)

---

개인적으로 레벨 0이라기엔 조금 어렵지않나.. 라는 생각이..
내가 아직 초보구나를 깨달은 문제였다 😢