Python으로 2D 행렬에서 0으로 채워진 모든 사각형 찾기

이진(binary) 값으로 구성된 2차원 행렬이 주어졌을 때, 0으로 채워진 모든 사각형의 시작 좌표와 끝 좌표를 찾는 문제를 생각해 봅시다. 여기서 중요한 조건은 각 사각형이 서로 분리되어 있어 서로 맞닿지 않는다는 점입니다. 다만 사각형은 배열의 경계와는 닿을 수 있으며, 요소가 하나뿐인 작은 사각형도 존재할 수 있습니다.

문제 예시

예를 들어 아래와 같은 입력 행렬이 주어졌다고 가정해 보겠습니다.

이 경우 기대되는 출력은 다음과 같습니다.

[[0, 1, 0, 1], [0, 5, 0, 5], [1, 2, 1, 2], [2, 3, 2, 4], [3, 1, 5, 1], [3, 4, 6, 5], [5, 3, 6, 5], [7, 1, 7, 1], [7, 5, 7, 5]]

여기서 각 내부 리스트는 [시작 행, 시작 열, 끝 행, 끝 열] 형태로, 하나의 0으로 채워진 사각형을 나타냅니다.

풀이 접근 방식

이 문제는 행렬을 순회하면서 아직 방문하지 않은 0을 발견할 때마다 해당 지점에서 오른쪽과 아래 방향으로 사각형의 경계를 확장해 나가는 방식으로 해결할 수 있습니다. 핵심 알고리즘은 다음과 같습니다.

1. find_rect() 함수를 정의합니다. 이 함수는 i, j, a(행렬), output(결과 저장), index를 인자로 받습니다.
2. x는 전체 행 개수, y는 전체 열 개수로 초기화합니다.
3. flag_col과 flag_row를 0으로 초기화하여, 각각 열과 행 방향에서 경계(1)를 만났는지 여부를 추적합니다.
4. m을 i부터 x-1까지 반복하며:
   • a[m][j]가 1이면 flag_row = 1로 설정하고 반복을 중단합니다.
   • a[m][j]가 5(이미 방문한 칸)이면 그대로 통과합니다.
   • n을 j부터 y-1까지 반복하며:
     • a[m][n]이 1이면 flag_col = 1로 설정하고 반복을 중단합니다.
     • 그렇지 않으면 a[m][n] = 5로 표시하여 재방문을 방지합니다.
5. 사각형의 끝 좌표 결정:
   • flag_row가 1이면 output[index]에 m-1을 추가하고, 아니라면 m을 추가합니다.
   • flag_col이 1이면 output[index]에 n-1을 추가하고, 아니라면 n을 추가합니다.
6. 메인 함수(get_coord)에서는:
   • n을 행렬의 크기로 설정합니다.
   • op라는 새로운 리스트와 idx = -1을 준비합니다.
   • i를 0부터 n까지, j를 0부터 첫 행의 길이까지 이중 반복하며, a[i][j] == 0일 때마다 [i, j]를 op에 추가하고 idx를 증가시킨 뒤 find_rect(i, j, a, op, idx)를 호출합니다.
7. 마지막으로 op를 출력합니다.

여기서 값 5는 이미 어떤 사각형에 포함된 칸임을 나타내는 임시 마커 역할을 하므로, 같은 영역이 중복 탐색되지 않습니다.

구현 코드

아래 코드를 통해 실제 동작 과정을 더 잘 이해할 수 있습니다.

def find_rect(i,j,a,output,index):
    x = len(a)
    y = len(a[0])
    flag_col = 0
    flag_row = 0
    for m in range(i,x):
        if a[m][j] == 1:
            flag_row = 1
            break
        if a[m][j] == 5:
            pass
        for n in range(j, y):
            if a[m][n] == 1:
                flag_col = 1
                break
            a[m][n] = 5
    if flag_row == 1:
        output[index].append( m-1)
    else:
        output[index].append(m)
    if flag_col == 1:
        output[index].append(n-1)
    else:
        output[index].append(n)

def get_coord(a):
    n = len(a)
    op = []
    idx = -1
    for i in range(0,n):
        for j in range(0, len(a[0])):
            if a[i][j] == 0:
                op.append([i, j])
                idx = idx + 1
                find_rect(i, j, a, op, idx)
    print (op)

tests = [[1, 0, 1, 1, 1, 0, 1],
         [1, 1, 0, 1, 1, 1, 1],
         [1, 1, 1, 0, 0, 1, 1],
         [1, 0, 1, 1, 0, 0, 1],
         [1, 0, 1, 1, 0, 1, 1],
         [1, 0, 1, 0, 0, 0, 0],
         [1, 1, 1, 0, 0, 0, 1],
         [1, 0, 1, 1, 1, 0, 1]]
get_coord(tests)

입력

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

출력

[[0, 1, 0, 1], [0, 5, 0, 5], [1, 2, 1, 2], [2, 3, 2, 4], [3, 1, 5, 1], [3, 4, 6, 5], [5, 3, 6, 5], [7, 1, 7, 1], [7, 5, 7, 5]]

정리

이 알고리즘은 행렬을 한 번 순회하면서 방문하지 않은 0을 만날 때마다 해당 사각형의 네 꼭짓점 정보를 수집하는 방식으로 동작합니다. 시간 복잡도는 최악의 경우 O(N × M)에 비례하며, 각 칸은 정확히 한 번씩만 처리되므로 효율적입니다. 이미지 처리나 도형 분석 분야에서 흰 배경 속 검은 영역을 찾는 등의 문제에 응용할 수 있습니다.