파이썬(Python)으로 이진 행렬에서 최대 경로 길이 찾기

이 문제에서는 각 요소가 0 또는 1로만 구성된 m×n 크기의 정사각형 행렬 mat[][]가 주어집니다. 값이 1인 요소는 연결된 상태를, 값이 0인 요소는 연결되지 않은 상태를 의미합니다. 우리의 목표는 이 이진 행렬에서 최대 경로 길이를 찾는 것입니다.

문제 설명

문제를 해결하려면 행렬 위에서 값이 1인 요소들로 이루어진 가장 긴 경로를 찾아야 합니다. 단, 경로를 탐색하기 전에 최대 한 개의 0을 1로 변환할 수 있다는 조건이 있습니다.

예시를 통해 문제를 자세히 이해해 보겠습니다.

입력

mat[][] = {{1, 0},
{0, 1}}

출력

3

설명

인덱스 (0, 1) 또는 (1, 0)에 있는 0을 1로 변환하면
경로 길이를 최대화할 수 있습니다.

위 예제에서 두 개의 1이 대각선으로 떨어져 있지만, 사이에 있는 0을 하나 1로 바꾸면 세 개의 1이 연결되어 길이 3의 경로가 만들어집니다.

해결 접근 방법

1. 단순한 접근법

가장 직관적인 방법은 행렬의 각 0을 하나씩 1로 바꿔 보면서 매번 경로 길이를 계산하는 것입니다. 깊이 우선 탐색(DFS)으로 경로 길이를 구하고, 모든 경우의 결과 중 최댓값을 반환하면 됩니다. 하지만 이 방식은 0의 개수만큼 전체 탐색을 반복해야 하므로 비효율적입니다.

2. 효율적인 접근법

더 효율적인 방법은 여러 번의 변환 시도를 반복하는 대신, 하나의 0을 1로 바꿀 때 가장 유망한 결과를 주는 지점을 한 번에 찾는 것입니다. 이를 위해 다음과 같은 단계로 진행합니다.

먼저 DFS를 사용해 연결된 1들의 그룹(연결 요소)을 식별하고, 각 그룹에 고유한 인덱스를 부여하며 그룹의 크기를 기록합니다. 그다음 각 0을 기준으로 상하좌우에 인접한 서로 다른 그룹들을 확인하고, 해당 0을 1로 바꿨을 때 연결되는 그룹 크기의 합에 1을 더한 값을 계산합니다. 이 값들 중 최댓값이 곧 최대 경로 길이가 됩니다.

솔루션의 동작을 보여주는 프로그램은 다음과 같습니다.

예제

def FindNeighbor(R, C, N):
    for nr, nc in ((R - 1, C), (R + 1, C), (R, C - 1), (R, C + 1)):
        if 0 <= nr < N and 0 <= nc < N:
            yield nr, nc


def DFSTraversal(R, C, index, mat, N):
    maxLen = 1
    mat[R][C] = index
    for nr, nc in FindNeighbor(R, C, N):
        if mat[nr][nc] == 1:
            maxLen += DFSTraversal(nr, nc, index, mat, N)
    return maxLen


def findLargestPath(mat):
    N = len(mat)
    maxPath = {}   # 그룹 인덱스 -> 그룹 크기 저장
    index = 2      # 0과 1과의 충돌을 피하기 위해 2부터 시작

    # 1단계: DFS로 각 연결 그룹의 크기를 계산
    for i in range(N):
        for j in range(N):
            if mat[i][j] == 1:
                maxPath[index] = DFSTraversal(i, j, index, mat, N)
                index += 1

    maxPathLen = max(maxPath.values() or [0])

    # 2단계: 각 0을 기준으로 인접한 서로 다른 그룹들을 연결
    for i in range(N):
        for j in range(N):
            if mat[i][j] == 0:
                seen = {mat[nr][nc] for nr, nc in FindNeighbor(i, j, N) if mat[nr][nc] > 1}
                maxPathLen = max(maxPathLen, 1 + sum(maxPath[g] for g in seen))

    return maxPathLen


I = [[1, 0], [0, 1]]
print('가장 긴 경로의 길이는 ' + str(findLargestPath(I)))

출력

가장 긴 경로의 길이는 3

코드 동작 원리

FindNeighbor 함수는 현재 셀 (R, C)의 상하좌우 인접 셀 좌표를 생성하며, 행렬 범위를 벗어나는 좌표는 제외합니다.

DFSTraversal 함수는 방문한 셀의 값을 그룹 인덱스로 변경하여 같은 그룹임을 표시하고, 재귀적으로 인접한 1들을 따라가며 그룹의 전체 크기를 반환합니다.

findLargestPath 함수는 먼저 전체 행렬을 순회하며 모든 연결 그룹의 크기를 딕셔너리에 기록합니다. 이후 각 0 셀을 검사하면서 인접한 서로 다른 그룹들의 크기를 집합(seen)으로 중복 없이 모으고, 해당 0을 1로 변환했을 때 얻을 수 있는 경로 길이(1 + 인접 그룹 크기의 합)를 계산해 최댓값을 갱신합니다.

이 접근법은 각 셀을 상수 번 방문하므로 전체 시간 복잡도는 O(N²) 수준으로, 매번 0을 하나씩 바꿔 가며 전체를 다시 탐색하는 단순한 방법보다 훨씬 효율적입니다.