code signal - 24. Minesweeper

Question

In the popular Minesweeper game you have a board with some mines and those cells that don't contain a mine have a number in it that indicates the total number of mines in the neighboring cells. Starting off with some arrangement of mines we want to create a Minesweeper game setup.

Example

For

matrix = [[true, false, false],
          [false, true, false],
          [false, false, false]]

the output should be

minesweeper(matrix) = [[1, 2, 1],
                       [2, 1, 1],
                       [1, 1, 1]]

Check out the image below for better understanding:

Input/Output

• [execution time limit] 4 seconds (py3)

• [input] array.array.integer image

  An image, stored as a rectangular matrix of non-negative integers.

  Guaranteed constraints: 3 ≤ image.length ≤ 100, 3 ≤ image[0].length ≤ 100, 0 ≤ image[i][j] ≤ 255.

• [output] array.array.integer

  • A blurred image represented as integers, obtained through the process in the description.

MY_ANSWER

def minesweeper(matrix):

    row = len(matrix)
    column = len(matrix[0])
    answer = [[0 for i in range(column)] for j in range(row)]
    pad_matrix = [[0 for i in range(column+2)] for j in range(row+2)] # 0을 패딩

    for i in range(row):
        for j in range(column):
            pad_matrix[i+1][j+1] = matrix[i][j]

    for x in range(row):
        for y in range(column):
            answer[x][y] = pad_matrix[x][y] + pad_matrix[x][y+1] + pad_matrix[x][y+2] + pad_matrix[x+1][y] + pad_matrix[x+1][y+2] + pad_matrix[x+2][y] + pad_matrix[x+2][y+1] + pad_matrix[x+2][y+2]

    
    return answer

• 지뢰 찾기 문제이다. 자신의 위치에서 상하좌우, 대각선 범위까지 지뢰의 수를 합한 것을 반환하는 matrix를 만들면 된다.

• 긴 코드이지만 원리는 간단하다. 정답을 반환할 빈 matrix를 만들어 준다.

  input matrix의 주변을 0으로 채운 padding matrix를 만든다. 자신의 위치를 기준으로 주위의 지뢰들을 센다.

  padding하지 않게 된다면 자신의 위치가 코너쪽에 있을 때 지뢰를 count할 때 error가 발생할 것이다.

Best_ANSWER

def minesweeper(matrix):

    r = []
    
    for i in range(len(matrix)):
        r.append([])
        for j in range(len(matrix[0])):
            l = -matrix[i][j] #지뢰가 있는 부분을
            for x in [-1,0,1]:
                for y in [-1,0,1]:
                    if 0<=i+x<len(matrix) and 0<=j+y<len(matrix[0]):
                        l += matrix[i+x][j+y]

            r[i].append(l)
    return r

• 나의 answer처럼 빈 matrix를 만든 뒤에 답을 채워넣는 방식이 아니라 for문을 돌면서 정답 matrix의 하나하나의 값을 채워가는 형식이다. input matrix는 아래와 같다고 하자

  

  그 후 True인 부분은 -1로 일단 매핑한다. if 조건에 따라서 범위에 넘어가지 않는 선에서 지뢰를 찾는다.

• 여기선 (0, 0) (0, 1) (1, 0)(1, 1) 에서 탐색 후 True(1)값이 2개가 더해져서 1이 될것이다.

  

• 그 후 차례로 for문을 반복하면

  

  다른 예제에서도 비슷하게 작동하는것을 알 수 있다.

  답을 보았지만.... 이해하기까지 너무 오래걸렸다.