16929: Two Dots

• 사이클이 존재하는 지 확인 -> dfs를 순회하면서, 처음 시작한 좌표로 돌아오는 경우가 있는 경우 "Yes" 출력하도록 구현하면 됨/ 해당 경우가 없는 경우는 "No" 출력

import sys
from collections import deque

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


def dfs(x, y, color, src_x, src_y, depth):
    if x < 0 or y < 0 or x >= N or y >= M:
        return

    if x == src_x and y == src_y and depth >= 4:
        print('Yes'); exit()
    
    if Map[x][y] == color:
        #print(Map[x][y], x, y)
        Map[x][y] = 0
        for i in range(4):
            dfs(x + dx[i], y + dy[i], color, src_x, src_y, depth+1)
        Map[x][y] = color


N, M = map(int, input().split(' '))
Map = []
for _ in range(N):
    Map.append(list(sys.stdin.readline()[:-1]))

for x in range(N):
    for y in range(M):
        if Map[x][y] != 0:
            dfs(x, y, Map[x][y], x, y, 0)
        else:
            continue
print('No')

• 2중 for문을 돌면서 Map에 있는 모든 cell을 순회했음 (시간 초과 안걸리니까 그냥 패스)
• dfs의 input parameter로 x, y (현재 좌표), color (시작점의 색깔), src_x, src_y (시작점의 좌표), depth를 넘겨줌
• 만약 depth가 4 이상이고, 현재 좌표와 시작점의 좌표가 일치하는 경우 print("Yes") 후, process 종료
• Map[x][y]이 color와 같다면, 상하좌우 탐색
  -> 방문한 cell은 0으로 변경해줌
  -> recursion은 stack형식임을 기억해야함 -> 이러한 특성을 통해 다음 depth의 dfs를 호출한 후, Map을 다시 원래의 색으로 복원해줌