프로그래머스 | Python | 안전지대

 

프로그래머스

 

내코드

def solution(board):
    answer = 0
    n = len(board)
    mine = [[0]*n for _ in range(n)]
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1),
                  (-1, -1), (-1, 1), (1, -1), (1, 1)]

    for i in range(n):
        for j in range(n):
            if board[i][j] == 1:  
                mine[i][j] = 1
                for dx, dy in directions:
                    ni, nj = i + dx, j + dy
                    if 0 <= ni < n and 0 <= nj < n:
                        mine[ni][nj] = 1
                        
    for i in mine:
        answer += i.count(0)
    return answer

코드설명

1. mine 배열 초기화:
   mine 배열은 0으로 초기화하여, 각 칸이 안전한지 아닌지를 나타내는 배열입니다. board와 동일한 크기를 가집니다.
2. 8방향 탐색:
   directions 리스트는 8방향(상, 하, 좌, 우, 대각선)을 나타냅니다. 이 리스트를 사용해 지뢰가 있는 칸 주변 8개 칸을 모두 위험 지역으로 표시합니다.
3. 지뢰 주변 탐색:
   board[i][j]가 1(지뢰)을 발견하면, 해당 칸과 그 주변 8개 칸을 mine 배열에 1로 표시합니다.
4. 안전 지역 계산:
   mine 배열에서 0인 안전한 지역을 계산하기 위해 count(0)을 사용하여 안전한 칸을 세고, 이를 answer에 더한 후 반환합니다.

특징

• 2차원 배열 탐색: 2차원 배열을 다루는 문제로, 각 칸을 순차적으로 확인하고 인접한 칸을 탐색해야 하는 특징이 있습니다.
• 효율적인 8방향 탐색: 지뢰를 찾은 후, 8방향으로 한 번에 탐색을 진행하는 방식으로 성능을 개선할 수 있습니다.
• 시간 복잡도: O(n^2)로, 배열 크기(n x n)만큼 두 번의 반복문을 돌며 처리합니다.

---

다른 코드

def solution(board):
    n = len(board)
    danger = set()
    for i, row in enumerate(board):
        for j, x in enumerate(row):
            if not x:
                continue
            danger.update((i+di, j+dj) for di in [-1,0,1] for dj in [-1, 0, 1])
    return n*n - sum(0 <= i < n and 0 <= j < n for i, j in danger)

코드설명

1. danger 집합 사용:
   danger는 위험한 칸들을 담는 집합으로, 중복을 허용하지 않아서 더 효율적으로 인접한 칸들을 추적할 수 있습니다.
2. 지뢰 인접한 칸 탐색:
   enumerate를 사용하여 board 배열을 순차적으로 탐색하면서, 지뢰가 있는 칸을 발견하면 그 주변의 8방향(상, 하, 좌, 우, 대각선)을 모두 danger 집합에 추가합니다.
3. 안전한 지역 계산:
   danger 집합에 포함되지 않은 칸들은 안전 지역으로, 이를 계산하기 위해 전체 칸에서 위험한 지역의 개수를 빼서 안전한 지역을 계산합니다.

특징

• 집합을 이용한 중복 제거: danger는 집합을 사용하여 중복을 자동으로 제거하고, 중복된 위험 지역을 효율적으로 처리합니다.
• 8방향 탐색: 8방향을 한 번에 탐색하여 각 지뢰의 주변 칸을 추가하는 방식으로 문제를 해결합니다.
• 시간 복잡도: O(n^2)로, 배열을 두 번 순차적으로 탐색합니다.

---

두 코드 비교

1. 배열 vs 집합:
   첫 번째 코드에서는 mine 배열을 사용해 각 칸을 추적하고, 위험 지역을 표시한 뒤 안전한 지역을 계산하는 방식입니다. 반면 두 번째 코드에서는 danger 집합을 사용하여 위험한 칸을 추적합니다. 집합은 중복을 자동으로 제거해 효율적인 탐색이 가능합니다.
2. 안전 지역 계산 방식:
   첫 번째 코드에서는 mine 배열을 순차적으로 탐색하며 안전한 칸을 세는 방식이고, 두 번째 코드에서는 전체 칸에서 위험한 지역의 개수를 빼는 방식으로 계산합니다.
3. 성능 차이:
   두 코드 모두 시간 복잡도는 O(n^2)로 동일하지만, 두 번째 코드에서 danger 집합을 사용한 방식이 메모리 사용을 조금 더 최적화할 수 있습니다. 집합을 사용하면 중복된 값을 자동으로 처리할 수 있기 때문입니다.

---

결론

• 첫 번째 코드는 각 칸을 추적하는 데 mine 배열을 사용하고, 안전 지역을 계산할 때 더 직관적이고 명확한 방식으로 해결할 수 있습니다. 그러나 배열을 한 번 더 사용하여 메모리 사용량이 늘어날 수 있습니다.
• 두 번째 코드는 집합을 사용하여 중복된 위험 지역을 자동으로 처리하며, 보다 간결하고 메모리 효율적으로 문제를 해결합니다.따라서, 메모리 사용을 최적화하고 중복을 처리하는 데 있어 두 번째 코드가 더 효율적이라 할 수 있습니다.