- Problem Link : https://www.acmicpc.net/problem/16929
문제
단순하게 설명하자면 같은 색의 점으로만 이동할 수 있는 그래프가 있다고 할 때 해당 그래프에서 순환하는 사이클이 만들어지는 여부를 확인하는 문제이다.
입력
- 첫째 줄, 게임판의 크기 N, M이 주어진다.
- 둘째 줄, N줄에 걸쳐 게임판의 상태가 주어진다.
출력
- 사이클이 있으면 'Yes' 없으면 'No'를 출력한다.
풀이
순환을 찾는다는 것은 그래프 상에서 결국 진행할 수 있는 노드로 진행하면서 내가 기존에 방문했던 노드를 또 다시 방문하게 되면 사이클을 찾았다고 할 수 있다. 결국 내가 방문할 수 있는 모든 노드를 방문해야하기 때문에 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")
