단순하게 설명하자면 같은 색의 점으로만 이동할 수 있는 그래프가 있다고 할 때 해당 그래프에서 순환하는 사이클이 만들어지는 여부를 확인하는 문제이다.
순환을 찾는다는 것은 그래프 상에서 결국 진행할 수 있는 노드로 진행하면서 내가 기존에 방문했던 노드를 또 다시 방문하게 되면 사이클을 찾았다고 할 수 있다. 결국 내가 방문할 수 있는 모든 노드를 방문해야하기 때문에 DFS 또는 BFS를 쓰는 문제인데 BFS는 이미 방문한 노드로는 다시 돌아오지 않기 때문에 이미 방문한 노드에 대해서 순환을 검사해야하는 이 문제에서는 적합하지 않다. 따라서 DFS 탐색 방식을 이용한다.
아래 코드를 보면 알겠지만 기본적인 틀은 DFS와 같고 dist라는 거리 배열을 추가로 만들어 시작점으로부터의 거리를 유지하면서 진행한다. 이 때 순환(사이클)은 어떻게 검사할 수 있을까? 순환이 만족하기 위해선 아래의 조건이 만족해야한다.
이미 방문한 노드로 다시 방문한다.
4개 이상의 노드로 이루어져야 한다.
모든 점의 색은 같다.
(시작 지점의 색을 매개변수로 전달받아 색이 같은 방향으로만 진행하도록 한다.)
순환의 각 원소들은 인접해야한다.
(그래프 탐색은 인접한 노드로만 이동하므로 이 부분도 자연스럽게 만족한다.)
방문 여부는 visited로 쉽게 확인할 수 있다. 세 번째, 네 번째 조건도 자연스럽게 만족하도록 코드를 작성했다. 중요한 점은 4개 이상의 노드라는 뜻이다. 노드가 4개일 때 아래 그림과 같이 dist 차이가 발생한다.
만약 순환이 커진다면 dist 차이는 더 커질 것이다. 즉, dist 차이가 3 이상이어야만 순환이 만족한다고 할 수 있을 것이다. 따라서 순환 여부를 아래의 조건문과 같이 작성할 수 있다.
if visited[ni][nj] and dist[ni][nj] >= dist[i][j] + 3:
이 문제에서 원하는 것은 순환의 존재 여부이므로 순환을 발견했다면 'Yes'를 출력하고 종료한다. 만약 모든 노드를 방문했음에도 순환이 발생하지 않는다면 'No'를 출력한다.
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = map(int, input().split())
# 하 우 상 좌
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
def dfs(i, j, start):
for d in range(4):
ni = i + di[d]
nj = j + dj[d]
if 0 <= ni < n and 0 <= nj < m and graph[ni][nj] == start:
if not visited[ni][nj]:
visited[ni][nj] = True
dist[ni][nj] = dist[i][j] + 1
dfs(ni, nj, start)
elif visited[ni][nj] and dist[ni][nj] >= dist[i][j] + 3:
print("Yes")
exit()
graph = []
for _ in range(n):
graph.append(input().strip())
dist = [[0 for _ in range(m)] for _ in range(n)]
visited = [[False] * m for _ in range(n)]
for i in range(n):
for j in range(m):
if not visited[i][j]:
dist[i][j] = 1
visited[i][j] = True
dfs(i, j, graph[i][j])
print("No")