문제 소개
2차원 이진 행렬이 주어졌을 때, 1은 폭탄이 있는 칸을, 0은 빈 칸을 의미합니다. 폭탄이 터지면 같은 행과 같은 열에 있는 모든 공간이 피해를 입게 됩니다. 우리가 구해야 할 것은 폭발로 인해 피해를 입지 않고 서 있을 수 있는 안전한 칸의 개수입니다.
예시
입력 행렬이 다음과 같다고 가정해 보겠습니다.
| 1 | 1 | 0 |
| 0 | 0 | 0 |
| 0 | 0 | 0 |
이 경우 출력값은 2입니다. 첫 번째 행에 폭탄이 두 개 있으므로 해당 행 전체와 각 폭탄이 위치한 열(0번 열, 1번 열)은 모두 위험합니다. 따라서 안전한 칸은 오른쪽 아래 끝 칸과 중간 행의 맨 오른쪽 칸, 즉 세 번째 열에 있는 두 칸뿐입니다.
풀이 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
행렬의 행 개수와 같은 크기의 불리언 리스트
r을 만들고 모두 False로 초기화합니다. 이 리스트는 해당 행에 폭탄이 있는지 여부를 나타냅니다.행렬의 열 개수와 같은 크기의 불리언 리스트
c를 만들고 모두 False로 초기화합니다. 이 리스트는 해당 열에 폭탄이 있는지 여부를 나타냅니다.행렬의 모든 칸을 순회하면서 값이 1인 칸을 발견하면, 그 칸이 속한 행과 열에 대응하는
r[i]와c[j]를 True로 설정합니다.안전한 칸의 개수를 셀 변수
ct를 0으로 초기화합니다.다시 행렬의 모든 칸을 순회하면서
r[i]와c[j]가 모두 False인 칸, 즉 폭탄이 없는 행과 열에 속한 칸이라면ct를 1씩 증가시킵니다.마지막으로
ct를 반환합니다.
이 알고리즘의 시간 복잡도는 O(n×m)으로, 행렬을 두 번 순회하기 때문에 효율적입니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
class Solution: def solve(self, matrix): r = [False for i in range(len(matrix))] c = [False for i in range(len(matrix[0]))] for i in range(len(matrix)): for j in range(len(matrix[0])): if matrix[i][j] == 1: r[i] = True c[j] = True ct = 0 for i in range(len(matrix)): for j in range(len(matrix[0])): if r[i] == False and c[j] == False: ct += 1 return ct ob = Solution() matrix = [ [1, 1, 0], [0, 0, 0], [0, 0, 0] ] print(ob.solve(matrix))
입력
[ [1, 1, 0], [0, 0, 0], [0, 0, 0] ]
출력
2
정리
핵심 아이디어는 폭탄의 영향 범위가 행과 열 단위로 퍼진다는 점입니다. 따라서 폭탄이 있는 행과 열만 미리 표시해 두면, 두 번째 순회에서 표시되지 않은 행과 열의 교차점만 세어 안전한 칸의 개수를 쉽게 구할 수 있습니다. 이 방식은 행렬의 크기가 커져도 선형 시간 안에 문제를 해결할 수 있어 실전에서도 유용하게 활용됩니다.