프로그래머스 | 안전지대 [파이썬 python]

프로그래머스

 

코드

import numpy as np

def solution(board):
    n = len(board)
    map = [[0]*(len(board)+2) for _ in range(len(board)+2)] # n+2 * n+2 행렬
    map = np.array(map)

    bomb = [] # 지뢰 위치 저장
    for i in range(n):
        for j in range(n):
            if board[i][j] == 1:
                bomb.append((i+1, j+1)) # map 기준 지뢰 위치
                map[i+1][j+1] = 1 # map에서 지뢰 표시
    #print(board)
    #print(map)
    #print(bomb)

    for i,j in bomb: # 지뢰 주변 지역
        map[i+1][j] = 1
        map[i-1][j] = 1
        map[i][j+1] = 1
        map[i][j-1] = 1
        map[i+1][j+1] = 1
        map[i+1][j-1] = 1
        map[i-1][j+1] = 1
        map[i-1][j-1] = 1
    #print(map)
    map = map[1:n+1,1:n+1] # board와 같은 크기로 슬라이싱
    #print(map)
    answer = n*n - np.sum(map) # 전체 칸 수 - 1의 개수(= 1을 다 더한 값)
    return int(answer)

진짜 코딩테스트에 이런 문제가 나오면 절대 이렇게 풀면 안 되겠지만 아직 내 수준은 여기다. BFS에 대해 공부하고 다시 풀어봐야지...

지난 구름 알고리즘에서 비슷한 문제를 풀어봐서 같은 방식으로 해결하였다.

 

n*n 행렬이 있을 때 가장 가장자리에 지뢰가 위치하면 주변 공간이 부족하기 때문에 indexError가 발생한다.

그래서 상하좌우 1열씩 증가시킨 n+2*n+2 행렬 map을 만들고, nd.array 형태로 바꿔주었다.

map은 0으로 가득 채워져 있어 모두 안전지대이다. 

board에서 지뢰가 위치한 위치를 찾아 그 점이 map에서 해당하는 인덱스를 bomb이라는 리스트에 저장해 주었다.

지뢰가 여러 개면 여러 쌍이 bomb에 존재하게 되는 것이다.

 

bomb에 있는 지뢰의 개수만큼 안전지대가 아닌 지뢰지대(지뢰 기준 상하좌우&대각선)를 찾아 1로 바꿔준다.

+1이 아니라 1로 지정하는 이유는 2개 이상의 지뢰에서 겹치는 지대가 있을 경우 각 지뢰별로 +1을 해주게 되면 2 이상의 숫자가 나오기 때문이다.

 

모든 지뢰지대를 체크했으면 map을 다시 원래 board의 크기로 슬라이싱 해준다.

그럼 전체 지대(n*n)에서 지뢰지대(np.sum(map))를 빼면 안전지대의 개수이다.

np.sum(map)을 해주는 이유는 지뢰지대는 모두 1로 표시했으므로 1의 총개수를 구하면 그 값이 바로 지뢰지대의 개수가 되는 것이다. 그렇기 때문에 sum을 해서 1들의 합을 구하는 것이다.

 

프로그래머스에서 바로 answer를 출력하면 (정수-numpy)를 했기 때문에 아래와 같은 에러가 발생한다.

TypeError: Object of type int64 is not JSON serializable

따라서 int 형으로 바꿔서 리턴해주면 문제없이 제출 가능하다.