Python으로 행렬에 배치된 폭탄이 모든 적을 제거하는지 확인하는 방법

행렬(mat)이 하나 주어져 있다고 가정해 봅시다. 이 행렬의 각 칸은 다음 세 가지 값 중 하나를 가질 수 있습니다.

• 0: 빈 공간
• 1: 폭탄
• 2: 적(Enemy)

폭탄이 터지면 폭발은 수평 방향과 수직 방향으로 양쪽 끝까지 확산됩니다. 따라서 우리가 확인해야 할 것은 폭탄이 폭발했을 때 행렬에 있는 모든 적이 제거되는지 여부입니다.

예를 들어 입력이 아래와 같다면,

출력은 True가 됩니다. [1, 1] 위치의 폭탄이 같은 열에 있는 [2, 1] 위치의 적을 제거하고, [0, 2] 위치의 적 역시 [3, 2] 위치의 폭탄에 의해 처리되기 때문입니다.

문제 해결 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다.

1. r := 행렬의 행(row) 개수로 설정합니다.
2. c := 행렬의 열(column) 개수로 설정합니다.
3. i := 0, j := 0, x := 0, y := 0으로 초기화합니다.
4. i를 0부터 r-1까지 반복합니다.
   • j를 0부터 c-1까지 반복합니다.
     • 만약 mat[i][j]가 1(폭탄)이라면:
       • x를 0부터 r-1까지 반복하며, mat[x][j]가 1이 아니면 0으로 변경합니다. 즉, 해당 열 전체를 소거합니다.
       • y를 0부터 c-1까지 반복하며, mat[i][y]가 1이 아니면 0으로 변경합니다. 즉, 해당 행 전체를 소거합니다.
5. 모든 폭탄을 처리한 후, 다시 전체 행렬을 탐색하면서 값이 2(적)인 칸이 하나라도 발견되면 False를 반환합니다.
6. 남아 있는 적이 없다면 True를 반환합니다.

핵심 아이디어는 각 폭탄이 자신이 속한 행과 열 전체를 커버한다는 점입니다. 폭탄 자체(값이 1인 칸)는 그대로 유지하면서 나머지 칸을 0으로 만들어 폭발 범위를 표시하고, 마지막에 적(2)이 남아 있는지만 검사하면 됩니다.

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

예제 코드

def solve(mat):
   r = len(mat)
   c = len(mat[0])
   i, j, x, y = 0, 0, 0, 0
   for i in range(r):
      for j in range(c):
         if mat[i][j] == 1:
            for x in range(r):
               if mat[x][j] != 1:
                  mat[x][j] = 0
            for y in range(c):
               if mat[i][y] != 1:
                  mat[i][y] = 0
   for i in range(r):
      for j in range(c):
         if mat[i][j] == 2:
            return False
   return True
matrix = [ [0,0,2,0], [0,1,0,0], [0,2,0,0], [0,0,1,0] ]
print(solve(matrix))

입력

[
[0,0,2,0],
[0,1,0,0],
[0,2,0,0],
[0,0,1,0]
]

출력

True

이 알고리즘의 시간 복잡도는 O(r × c × (r + c))입니다. 각 폭탄을 발견할 때마다 해당 행과 열 전체를 순회하기 때문입니다. 행렬의 크기가 크지 않다면 충분히 실용적인 방법이며, 문제의 요구사항을 직관적으로 해결할 수 있습니다.