BOJ 16929 - Two Dots (Python)

G4, DFS

---

문제 설명

Two Dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.

각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.

다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다.

점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다.

• 모든 k개의 점은 서로 다르다.
• k는 4보다 크거나 같다.
• 모든 점의 색은 같다.
• 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.

제한 사항

• 2 ≤ N, M ≤ 50

입력

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다.

출력

사이클이 존재하는 경우에는 "Yes", 없는 경우에는 "No"를 출력한다.

입력 예시

3 4
AAAA
ABCA
AAAA

출력 예시

Yes

---

풀이

cycle을 이루는 dfs 탐색 문제이다.
직전 탐색 위치를 저장해놓고 재귀하기 위해 px, py parameter를 사용했다.

import sys
sys.setrecursionlimit(10**8)

n, m = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
    graph.append(list(sys.stdin.readline().rstrip()))

visited = [[0] * m for _ in range(n)]

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

def dfs(x, y, color, px, py):
    if visited[x][y]:   # 방문했던 점을 다시 dfs로 탬색?
        print("Yes")    # cycle을 이룬다.
        exit()

    visited[x][y] = 1

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0<=nx<n and 0<=ny<m and graph[nx][ny] == color:
            if (nx, ny) != (px, py):        # 직전 탐색 위치는 탐색할 필요 없음
                dfs(nx, ny, color, x, y)

for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            dfs(i, j, graph[i][j], -1, -1)

print("No")