Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 2차원 행렬에서 순환(Cycle) 존재 여부 확인하기

문제 개요

2차원 행렬이 주어졌을 때, 임의의 칸에서 출발하여 같은 값을 가진 인접한 칸(위, 아래, 왼쪽, 오른쪽)으로만 이동한 뒤, 다시 시작 지점으로 돌아올 수 있는지 확인하는 문제입니다. 단, 바로 직전에 방문했던 칸으로는 되돌아갈 수 없다는 제약 조건이 있습니다.

예를 들어 다음과 같은 행렬이 입력으로 주어진다고 가정해 보겠습니다.

2
2
2
1
2
1
2
1
2
2
2
1

이 경우 출력은 True가 됩니다. 값이 2인 칸들을 따라 이동하면 시작 지점으로 되돌아오는 순환 경로를 만들 수 있기 때문입니다.

해결 접근 방법

이 문제는 그래프 탐색 기법인 DFS(깊이 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • R := 행렬의 행(row) 개수
  • C := 행렬의 열(column) 개수
  • vis := R x C 크기의 방문 여부 행렬을 만들고 False로 초기화
  • dfs() 함수를 정의합니다. 이 함수는 시작 좌표 root를 인자로 받습니다.
    • stack := root와 None 두 요소를 가진 스택을 생성
    • vis[root[0]][root[1]] := True로 방문 처리
    • 스택이 비어 있지 않은 동안 다음을 반복합니다.
      • [v, prev] := 스택의 최상단 요소를 꺼냄(pop)
      • v의 각 이웃 w에 대해 다음을 검사합니다.
        • w가 prev(직전 노드)와 다른 경우:
          • vis[w[0]][w[1]]이 False라면 → True로 방문 처리 후 [w, v]를 스택에 push
          • 이미 방문한 상태라면 → 사이클이 존재하므로 True 반환
    • 반복이 끝나면 False 반환
  • 메인 로직에서는 모든 칸을 순회하며 아직 방문하지 않은 칸에서 dfs()를 호출하고, True가 반환되면 즉시 True를 반환합니다.
  • 모든 칸을 확인해도 사이클을 찾지 못했다면 False를 반환합니다.

여기서 중요한 포인트는 각 노드를 스택에 저장할 때 직전 노드(prev) 정보를 함께 저장한다는 것입니다. 이를 통해 양방향 인접 관계에서 발생하는 '왕복'을 사이클로 오판하는 오류를 방지할 수 있습니다.

구현 예제

아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.

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

코드 설명

  • get_neighbors(): 현재 위치 (i, j)에서 상하좌우로 이동 가능한 칸 중, 행렬 범위 안에 있고 값이 동일한 칸만 생성자(yield)로 반환합니다.
  • vis 배열: 각 칸의 방문 여부를 추적하여 무한 루프를 방지합니다.
  • dfs(): 명시적 스택을 사용한 반복형 DFS로, 재귀 깊이 제한(recursion limit) 문제 없이 큰 행렬에서도 안전하게 동작합니다.

실행 결과

입력

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

출력

True

복잡도 분석

  • 시간 복잡도: O(R × C) — 각 칸은 최대 한 번씩만 방문됩니다.
  • 공간 복잡도: O(R × C) — 방문 여부 배열과 스택에 필요한 공간입니다.

이처럼 DFS와 직전 노드 추적 기법을 결합하면, 격자 형태의 행렬에서 같은 값으로 이루어진 순환 구조를 간단하고 효율적으로 판별할 수 있습니다.