[Python] 백준 <16929-Two Dots>

https://www.acmicpc.net/problem/16929

 

import sys
input = sys.stdin.readline

def dfs(a, b, s, c):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    area = 1

    for i in range(4):
        nx, ny = a+dx[i], b+dy[i]
        if 0 <= nx < N and 0 <= ny < M and game[nx][ny] == s and visited[nx][ny] == 0:
            visited[nx][ny] = c
            area += dfs(nx, ny, s, c)
    return area

def check_cycle(x, y, from_x, from_y, c, s):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < M and game[nx][ny] == s:
            # 바로 직전 노드는 제외
            if nx == from_x and ny == from_y:
                continue  
            # 사이클 발견
            if visited_cycle[nx][ny] == c:
                return True  
            # 아직 방문안한 곳이 있으면 방문하고 사이클 체크
            if visited_cycle[nx][ny] == 0:
                visited_cycle[nx][ny] = c
                if check_cycle(nx, ny, x, y, c, s):
                    return True
    # 끝까지 사이클이 없으면 False 반환
    return False

N, M = map(int, input().split(" "))
game = list()
for _ in range(N):
    game.append(list(input().strip()))

# 붙어있는 같은 색깔의 구역 표시
visited = [[0]*M for _ in range(N)]
cnt = 0
area_li = dict()
for i in range(N):
    for j in range(M):
        if visited[i][j] == 0:
            cnt += 1
            visited[i][j] = cnt
            # 순서대로 i, j, 색깔, 구역 번호
            area_size = dfs(i, j, game[i][j], cnt)
            area_li[cnt] = area_size

# 크기가 4 이상인 구역을 대상으로 사이클을 만들수 있는지 체크
visited_cycle = [[0]*M for _ in range(N)]
dap = False
for i in range(N):
    for j in range(M):
        area_num = visited[i][j]
        # 크기가 4이상이고 방문하지 않았으면 체크
        # 한 곳이라도 사이클이 존재하면 반복문 종료
        if area_li[area_num] >= 4 and visited_cycle[i][j] == 0:
            visited_cycle[i][j] = area_num
            # 순서대로 i, j, 이전 좌표 x, y, 구역 번호, 색깔
            if check_cycle(i, j, -1, -1, area_num, game[i][j]):
                dap = True
                break

if dap:
    print("Yes")
else:
    print("No")