문제 정의
0은 빈 칸을, 1은 도형을 이루는 블록을 의미하는 이진 행렬(binary matrix)이 주어졌을 때, 이 도형의 둘레(perimeter)를 계산하는 것이 목표입니다. 단, 도형 내부에는 구멍이 없다고 가정합니다.
예를 들어 입력 행렬이 다음과 같다면,
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
출력 결과는 14가 됩니다.
접근 방법
핵심 아이디어는 간단합니다. 모든 블록은 기본적으로 네 변을 가지므로, 처음에는 각 블록이 둘레에 4만큼 기여한다고 생각합니다. 그러나 상하좌우로 인접한 셀에도 블록이 있다면, 서로 맞닿아 있는 변은 외곽 경계가 아니기 때문에 둘레에서 제외해야 합니다. 따라서 인접한 블록 하나당 기여분을 1씩 감소시키면 최종 둘레를 구할 수 있습니다.
알고리즘을 단계별로 정리하면 다음과 같습니다.
d := 0, perimeter := 0 으로 초기화합니다.
height := 행렬의 행 개수, length := 행렬의 열 개수로 설정합니다.
행렬의 각 행(line)에 대해 반복합니다.
c := 0 으로 초기화합니다.
행의 각 값(val)에 대해 반복합니다.
val이 1이라면 surround := 4로 설정합니다.
c가 length - 1이 아니면서 matrix[d][c + 1]이 1이면 surround를 1 감소시킵니다. (오른쪽 인접)
c가 0이 아니면서 matrix[d][c - 1]이 1이면 surround를 1 감소시킵니다. (왼쪽 인접)
d가 height - 1이 아니면서 matrix[d + 1][c]가 1이면 surround를 1 감소시킵니다. (아래쪽 인접)
d가 0이 아니면서 matrix[d - 1][c]가 1이면 surround를 1 감소시킵니다. (위쪽 인접)
surround 값을 perimeter에 더하고 c를 1 증가시킵니다.
한 행의 순회가 끝나면 d를 1 증가시킵니다.
모든 순회가 끝나면 perimeter를 반환합니다.
예제 코드
아래 파이썬 구현을 통해 동작 방식을 더 자세히 살펴보겠습니다.
class Solution:
def solve(self, matrix):
d = 0
perimeter = 0
height = len(matrix)
length = len(matrix[0])
for line in matrix:
c = 0
for val in line:
if val == 1:
surround = 4
if c != length - 1:
if matrix[d][c + 1] == 1:
surround -= 1
if c != 0:
if matrix[d][c - 1] == 1:
surround -= 1
if d != height - 1:
if matrix[d + 1][c] == 1:
surround -= 1
if d != 0:
if matrix[d - 1][c] == 1:
surround -= 1
perimeter += surround
c += 1
d += 1
return perimeter
ob = Solution()
matrix = [
[0,0,0,0,0],
[0,0,1,1,1],
[0,0,1,1,0],
[0,1,1,1,0],
[0,0,0,0,0]
]
print(ob.solve(matrix))입력
matrix = [ [0,0,0,0,0], [0,0,1,1,1], [0,0,1,1,0], [0,1,1,1,0], [0,0,0,0,0]]
출력
14
복잡도 분석
이 알고리즘은 행렬의 모든 셀을 한 번씩만 확인하므로 시간 복잡도는 O(H × W)입니다. 여기서 H는 행 개수, W는 열 개수입니다. 또한 추가적인 저장 공간 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)로 매우 효율적입니다.