[백준]16929 : Two Dots

DFS

문제: Two-Dots

dfs 문제입니다. 먼저, 사이클이 만들어지기 위해서는 어떤 조건이 있는지 확인해봅니다.
1. 시작점과 끝점이 같아야한다.
2. k는 4보다 크거나 같다.
즉 방문하는 점이 4개 이상이고 시작점과 끝점이 같으면 사이클을 이룬다는 것입니다.

그러니 노드 순서대로 dfs를 돌릴 때 들어가야 할 요소들은 시작점, 끝점(중간점), 갯수 이겠죠?
dfs 를 바로 리턴하는 경우는 사이클이 만들어지거나, 시작점과 끝점이 같고, 갯수가 4개 이상일 때 입니다.
1. 중간점의 다음점이 방문하지 않았고, 중간점과 다음점의 색이 같은 경우는 갯수를 하나 증가 시키고 dfs를 돌 수있습니다.
2. 다음점이 시작점과 같고 갯수가 4개 이상이면 --> 종료조건이겠죠? 그래서 카운트를 증가시키지 않고 한번 더 재귀를 실행해서 종료조건에 이르게 합니다.

~~개인적으로 시작점과 끝점을 매개변수에 모두 넣는 다는 것이 신선한 문제였습니다. ~~

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for i in range(n):
	graph.append(list(map(str, sys.stdin.readline().rstrip())))
cycle = False
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(start_x, start_y, tmp_x, tmp_y, cnt):
	global cycle
    #사이클 생성되면 바로 종료
	if cycle:
		return
    # 사이클 생성됐는지 확인 
	visited[tmp_x][tmp_y] = True
	if tmp_x == start_x and tmp_y == start_y and cnt >= 4:
		cycle = True
		return
	for i in range(4):
		nx = tmp_x + dx[i]
		ny = tmp_y + dy[i]
		if nx < 0 or ny < 0 or nx >= n or ny >= m:
			continue
        # dfs 이어가는 조건
		if not visited[nx][ny] and graph[nx][ny] == graph[tmp_x][tmp_y]:
			visited[nx][ny] = True
			dfs(start_x, start_y, nx, ny, cnt+1)
        # dfs 끝내려는 조건 
		elif nx == start_x and ny == start_y  and cnt >= 4:
			dfs(start_x, start_y, nx, ny, cnt)
	return

for i in range(n):
	for j in range(m):
		visited = [[False]*m for _ in range(n)]
		tmp_x = i
		tmp_y = j
        # 시작점, 중간점, 갯수 
		dfs(i, j, tmp_x, tmp_y, 1)
if cycle:
	print('Yes')
else:
	print('No')