Python의 이진 행렬에서 최대 경로 길이 찾기

이 문제에서는 각 요소가 0 또는 1인 크기 m X n의 정방 행렬 mat[][]이 제공됩니다. 요소의 값이 1이면 연결되어 있다는 의미이고 값이 0이면 연결되어 있음을 의미합니다. 연결되지 않습니다. 우리의 임무는 이진 행렬에서 최대 경로 길이를 찾는 것입니다.

문제 설명 − 문제를 해결하려면 행렬에서 가장 큰 길이의 경로를 찾아야 합니다. 즉, 행렬의 모든 1개 요소를 의미합니다. 경로를 찾기 전에 최대 1개를 0에서 1로 변환합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력

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

출력

3

설명

We can convert 0 at index (0, 1) or (1, 0) to maximise the path length.

솔루션 접근 방식

이 문제에 대한 간단한 해결책은 각각을 0에서 1로 변환한 후 길이를 찾는 것입니다. 경로의 길이를 찾기 위해 깊이 우선 탐색을 사용하고 모든 경로 길이의 최대값을 반환합니다.

효율적인 솔루션은 여러 변환을 수행할 필요를 없애고 가장 유망한 솔루션을 제공하는 것으로 정착하는 것입니다. 하나를 0에서 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)

   return maxLen


def findLargestPath(mat):

   N = len(mat)
   maxPath = {}
   index = 2

   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])

   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[i] for i in seen))

   return maxPathLen
I = [[1, 0], [0, 1]]
print("The length of largest path is " + str(findLargestPath(I)))

출력

The length of largest path is 3