행렬의 일부 요소를 확인하는 프로그램이 파이썬에서 순환을 형성하는지 여부

2차원 행렬이 있다고 가정합니다. 어떤 셀에서 시작하여 같은 값의 인접한 셀(위, 아래, 왼쪽, 오른쪽)을 이동하고 같은 시작점으로 돌아올 수 있는지 확인해야 합니다. 마지막으로 방문한 셀은 다시 방문할 수 없습니다.

따라서 입력이 다음과 같으면

그러면 2초를 따라 주기를 형성할 수 있으므로 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• R :=행렬의 행 수
• C :=행렬의 열 개수
• vis :=R x C 크기의 행렬을 만들고 False로 채움
• dfs() 함수를 정의합니다. 이것은 뿌리를 내릴 것입니다
• stack :=root와 null 두 개의 요소가 있는 스택
• vis[루트[0], 루트[1]] :=참
• 스택이 비어 있지 않은 동안 수행
  • [v, prev] :=스택의 최상위 요소, 스택에서 팝
  • v의 각 이웃 w에 대해 다음을 수행합니다.
    • w가 prev와 같지 않으면
      • vis[w[0], w[1]]가 거짓이면
        • vis[w[0], w[1]] :=참
        • 스택에 [w, v] 푸시
    • 그렇지 않으면
      • 참 반환
• 거짓을 반환
• 기본 방법에서 다음을 수행합니다.
• 0 ~ R - 1 범위의 i에 대해
  • 0 ~ C - 1 범위의 j에 대해 다음을 수행합니다.
    • vis[i, j]가 거짓이면
      • dfs((i, j))가 참이면
        • 참 반환
• 거짓을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, matrix):
      R = len(matrix)
      C = len(matrix[0])

      def get_neighbors(i, j):
         val = matrix[i][j]
         for ii, jj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
            if 0 <= ii < R and 0 <= jj < C and matrix[ii][jj] == val:
               yield ii, jj

      vis = [[False] * C for _ in range(R)]

      def dfs(root):
         stack = [(root, None)]
         vis[root[0]][root[1]] = True
         while stack:
            v, prev = stack.pop()
            for w in get_neighbors(*v):
               if w != prev:
                  if not vis[w[0]][w[1]]:
                     vis[w[0]][w[1]] = True
                     stack.append((w, v))
                  else:
                     return True
         return False

      for i in range(R):
         for j in range(C):
            if not vis[i][j]:
               if dfs((i, j)):
                  return True
      return False
     
ob = Solution()
matrix = [
   [2, 2, 2, 1],
   [2, 1, 2, 1],
   [2, 2, 2, 1]
]
print(ob.solve(matrix))

입력

[  
[2, 2, 2, 1],  
[2, 1, 2, 1],  
[2, 2, 2, 1] ]

출력

True