이번 문제는 깊이우선탐색을 통해 해결하였다. 깊이우선탐색을 하는 과정에서 사이클의 조건을 생각하는데에 시간이 조금 걸렸다. 사이클의 조건은 다음과 같이 도출되었다.

• 길이가 4 이상이다.
• 다음 탐색하고자 하는 위치가 시작 위치와 같다.

탐색 도중에 위의 조건에 만족할 경우 Yes를 출력할 수 있도록 값을 갱신하였다. 그리고 또 중요한 것은 재귀호출을 하기 전에 탐색할 다음 노드의 방문처리를 해준 뒤에 재귀호출 이후에 다시 방문 전으로 바꿔주어 다음 탐색 시에 영향이 없도록 해야 한다.

• dfs함수를 y, x, sy, sx, cnt를 인자로 갖도록 선언한다. 이때 y, x는 현재의 좌표이고, sy, sx는 탐색 시작 좌표이며, cnt는 현재 길이를 의미한다.
  -> answer를 global로 선언한다.
  -> 4가지 방향을 dy, dx에 짝지어 저장한다.
  -> 4번 반복하는 i에 대한 for문을 돌린다.
  --> ny를 y+dy[i]로 저장한다.
  --> nx를 x+dx[i]로 저장한다.
  --> 만약 ny, nx가 0보다 크거나 같고, ny가 n보다 작고, nx가 m보다 작을 경우,
  ---> 만약 board[ny][nx]가 board[y][x]와 같고 visited[ny][nx]가 False일 경우,
  ----> visited[ny][nx]를 True로 갱신한다.
  ----> dfs(ny, nx, sy, sx, cnt+1)을 재귀호출한다.
  ----> visited[ny][nx]를 False로 갱신한다.
  ---> 만약 cnt가 4보다 크거나 같고, sy가 ny와 같고, sx가 nx와 같을 경우,
  ----> answer를 Yes로 갱신한다.
  ----> True를 반환한다.
  ---> 만약 answer가 Yes일 경우,
  ----> 함수를 종료한다.
  -> False를 반환한다.
• n, m을 입력받는다.
• 게임판의 정보를 담을 리스트 board를 선언한다.
• n번 반복하는 for문을 돌린다.
  -> board를 입력받는다.
• visited를 False n*m으로 채운다.
• answer를 No로 선언한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> m번 반복하는 j에 대한 for문을 돌린다.
  --> visited[i][j]를 True로 갱신한다.
  --> dfs(i, j, i, j, 1)을 호출한다.
  --> 만약 answer가 Yes일 경우 반복문을 탈출한다.
• answer를 출력한다.

Code

def dfs(y, x, sy, sx, cnt):
    global answer
    dy=[0, 0, -1, 1]
    dx=[1, -1, 0, 0]
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if ny>=0 and nx>=0 and ny<n and nx<m:
            if board[ny][nx]==board[y][x] and visited[ny][nx]==False:
                visited[ny][nx]=True
                dfs(ny, nx, sy, sx, cnt+1)
                visited[ny][nx]=False
            if cnt>=4 and sy==ny and sx==nx:
                answer='Yes'
                return True
            if answer=='Yes':
                return
    return False
n, m=map(int, input().split())
board=[]
for _ in range(n):
    board.append(list(map(str, input())))
visited=[[False]*m for _ in range(n)]
answer='No'
for i in range(n):
    for j in range(m):
        visited[i][j]=True
        dfs(i, j, i, j, 1)
        if answer=='Yes':
            break
print(answer)