[백준][Python] 16929 two_dots

싸이클을 만들 수 있느냐는 문제

조건은

1. 이전칸으로 가지 않을 것

2. 이전칸을 제외하고 방문했던 지점을 만나면 싸이클이 존재.

N,M=map(int,input().split())
matrix=[list(map(str,input()))for _ in range(N)]
visited = [[False]*M for _ in range(N)]

dy=[0,0,1,-1]
dx=[1,-1,0,0]


# 싸이클의 조건
# 1. 바로 이전 칸으로 가지 말 것( 이전 좌표 가억해두고 같으면 이동하지말것.)
# 2. 그럼에도 불구하고 갔던 곳(visited true)를 만나면 싸이클이 존재하므로 True를 반환할것.
def dfs(x,y,px,py,ball):
    if visited[x][y]==True:
        return True
    visited[x][y]=True

    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx!=px or ny!=py:
            # 색깔이 같은곳만 들어갈 것.
            if 0<=nx<N and 0<=ny<M and matrix[nx][ny]==ball :
                # 그냥 dfs돌리지말고 if true 넣어서 되돌아오는 재귀 막을것.
                if dfs(nx,ny,x,y,ball): 
                    return True
    # 재귀 다끝났는데(사방 막혔는데) true안찍혔으면 망한것.
    return False

# 모든 정점에서 시작해보는데 방문한곳은 검사 다 끝났으니 갈 필요 없음.
for i in range(N):
    for j in range(M):
        if visited[i][j]:
            continue
            # 시작지점, 이전좌표, 색깔.
        if dfs(i,j,0,0,matrix[i][j]):
            print("Yes")
            exit() 
print("No")