백준 16929 파이썬 - Two Dots

https://www.acmicpc.net/problem/16929

16929번: Two Dots

문제

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

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

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

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

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

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

코드

import sys
n, m = map(int, sys.stdin.readline().split())
arr = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
flag = False
visited = [[False] * m for _ in range(n)]
def dfs(y, x, y1, x1, dot):
    if visited[y][x]:
        return True
    visited[y][x] = True
    for i in range(4):
        a = y + dy[i]
        b = x + dx[i]
        if a != y1 or b != x1:
            if 0 <= a < n and 0 <= b < m and arr[a][b] == dot:
                if dfs(a, b, y, x, dot):
                    return True
    return False
for i in range(n):
    for j in range(m):
        if visited[i][j]:
            continue
        if dfs(i, j, 0, 0, arr[i][j]):
            flag = True
            break
print("Yes" if flag else "No")

풀이

계속 dfs로 탐색한다. 색이 같은 서로 다른 점 중 범위에 있는 점을 탐색한다. 

dfs함수의 첫 줄의 if문은 탐색하다가 이미 방문한 곳을 찾으면 True를 리턴한다는 것이다. 이 것은 사이클이 존재한다는 것을 뜻한다.