16929번 Two Dots

문제

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

접근 방식

DFS로 사이클이 존재하는지 판별하면 된다.

처음에는 처음 DFS 탐색을 시작하는 위치를 넣어서 했다가, 해당 위치와 꼭 만난다는 보장이 없다는 사실을 깨닫고 (..)

방문한 목록에 있는지 확인하는 방식으로 수정했더니 역시 갔던 방향으로 도로 갈 수 있어서 틀렸다.

갔던 방향으로 가지 않으며 + 방문 표시 여부에 따라 답을 찾기 위해서는 이전 위치 정보를 함께 넘겨서 확인해야 한다.

코드

import sys
sys.setrecursionlimit(10**5)

isCycle = False


# 직전 노드와 현재 노드 함께 넘겨줘서 왔던 방향으로 가지 않게끔 한다
def dfs_find_cycle(px, py, cx, cy, v):
    v.add((cx, cy))
    for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
    	# 이전 위치와 다른 위치 + 같은 색인 경우
        if 0 <= cx + dx < n and 0 <= cy + dy < m and (cx + dx, cy + dy) != (px, py) and MAP[cx + dx][cy + dy] == MAP[cx][cy]:
            if (cx + dx, cy + dy) not in v:
                dfs_find_cycle(cx, cy, cx + dx, cy + dy, v)
            elif (cx + dx, cy + dy) in v and len(v) >= 4:  # 4개 이상 방문 + 방문 목록에 있는 경우 사이클 존재
                global isCycle
                isCycle = True
                return


n, m = map(int, input().split())
MAP = [input() for _ in range(n)]

visited = set()
for i in range(n):
    for j in range(m):
        if (i, j) not in visited:
            dfs_find_cycle(-1, -1, i, j, visited)  # 이전 위치, 현재 위치, 점 개수 함께

print("Yes") if isCycle else print("No")