문제: 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')