파이썬으로 2D 그리드에서 사이클 감지하는 프로그램 작성하기

문제 소개

m × n 크기의 문자로 구성된 2차원 배열 grid가 주어졌을 때, 그리드 안에 사이클(cycle)이 존재하는지 판별하는 프로그램을 파이썬으로 작성해 보겠습니다.

여기서 사이클이란 길이가 4 이상이면서 시작 지점과 끝 지점이 같은 경로를 의미합니다. 이동은 상·하·좌·우 네 방향으로만 가능하고, 이동하려는 칸은 반드시 현재 칸과 같은 값을 가져야 하며, 한 번 방문한 칸은 다시 방문할 수 없습니다.

예시

다음과 같은 4×4 그리드가 입력으로 주어졌다고 가정해 봅시다.

m	m	m	p
m	k	m	m
m	m	s	m
f	m	m	m

이때 출력은 True입니다. 초록색으로 표시된 'm' 칸들이 서로 연결되어 하나의 고리, 즉 사이클을 이루기 때문입니다.

풀이 접근: DFS와 3색 마킹 기법

이 문제는 그래프 이론에서 사이클을 찾을 때 널리 사용되는 깊이 우선 탐색(DFS)과 3색 마킹 기법으로 효율적으로 해결할 수 있습니다. 각 칸의 상태를 세 가지 색으로 구분합니다.

WHITE(0): 아직 방문하지 않은 칸
GRAY(1): 현재 탐색 중인 경로에 포함된 칸
BLACK(2): 탐색이 완료된 칸

탐색 도중 인접한 칸에서 GRAY 상태의 칸을 다시 만난다면, 현재 진행 중인 경로로 되돌아갈 수 있다는 뜻이므로 사이클이 존재합니다. 단, 바로 직전에 지나온 부모 칸은 제외해야 합니다. 두 칸 사이를 단순히 왕복하는 것만으로는 사이클이 아니기 때문입니다.

알고리즘 단계

WHITE := 0, GRAY := 1, BLACK := 2로 초기화합니다.
R := 그리드의 행 개수, C := 열 개수로 설정합니다.
color := 기본값이 0(WHITE)인 맵(딕셔너리)을 준비합니다.
dfs(r, c, pr = -1, pc = -1) 함수를 정의합니다. pr, pc는 직전에 방문한 부모 칸의 좌표입니다.
1. color[r, c] := GRAY로 설정합니다.
2. 네 방향 (x, y) 각각에 대해 다음을 수행합니다.
  1. (nr, nc) := (r + x, c + y)로 인접 칸의 좌표를 계산합니다.
  2. nr, nc가 그리드 범위 안에 있고, grid[r][c]와 grid[nr][nc]의 값이 같으며, (nr, nc)가 부모 칸 (pr, pc)가 아니라면:
    1. color[nr, nc]가 WHITE이면 dfs(nr, nc, r, c)를 재귀 호출하고, 결과가 True이면 True를 반환합니다.
    2. color[nr, nc]가 GRAY이면 사이클을 발견한 것이므로 True를 반환합니다.
3. 모든 방향을 확인한 뒤 color[r, c] := BLACK으로 갱신하고 False를 반환합니다.
메인 루틴에서는 모든 칸 (r, c)를 순회하면서 color[r, c]가 WHITE인 칸에서 dfs(r, c)를 호출하고, True가 반환되면 즉시 True를 반환합니다.
모든 칸을 확인했는데도 사이클을 찾지 못했다면 False를 반환합니다.

파이썬 구현 코드

다음 구현을 통해 위 알고리즘이 실제로 어떻게 동작하는지 확인해 보겠습니다.

from collections import defaultdict

di = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def solve(grid):
    WHITE, GRAY, BLACK = 0, 1, 2
    R, C = len(grid), len(grid[0])
    color = defaultdict(int)

    def dfs(r, c, pr=-1, pc=-1):
        color[r, c] = GRAY
        for x, y in di:
            nr, nc = r + x, c + y
            if (0 <= nr < R and 0 <= nc < C
                    and grid[r][c] == grid[nr][nc]
                    and (nr, nc) != (pr, pc)):
                if color[nr, nc] == WHITE:
                    if dfs(nr, nc, r, c):
                        return True
                elif color[nr, nc] == GRAY:
                    return True
        color[r, c] = BLACK
        return False

    for r in range(R):
        for c in range(C):
            if color[r, c] == WHITE:
                if dfs(r, c):
                    return True
    return False

matrix = [["m", "m", "m", "p"],
          ["m", "k", "m", "m"],
          ["m", "m", "s", "m"],
          ["f", "m", "m", "m"]]
print(solve(matrix))

실행 결과

입력:

[["m", "m", "m", "p"], ["m", "k", "m", "m"], ["m", "m", "s", "m"], ["f", "m", "m", "m"]]

출력:

True

복잡도 분석

각 칸은 최대 한 번씩만 방문되므로 시간 복잡도는 O(m × n)이며, 색상 정보를 저장하는 맵 역시 칸 수에 비례해 늘어나므로 공간 복잡도 또한 O(m × n)입니다.