Python 16929번 Two Dots

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

16929번: Two Dots

 

문제를 처음 풀때 graph로 딕셔너리를 만들어서 풀려고 했는데

예시의 경우에선 답이 잘나오는데 중간에 예외적인 경우에서 오답처리가 돼서 좀 오랫동안 고민하다가 그냥 dfs의 재귀만 이용해서 풀었더니 정답이 되었다....ㅠ

풀이 방법은 먼저 방문했는지 확인하기 위해 visited라는 2차원 배열을 만들고 현재 칸을 방문했다는 것을 저장하기 위해 visited값을 바꿔주고

그 다음 이제 현재 칸에서 상하좌우로 이동하는데 이동하는 경우는 값이 같고 틀을 벗어나지 않고 이전값들과 같지 않으면 그 방향으로 한칸 이동한다.

그리고 만약 이동한 칸이 방문한 적이 있고 cnt값이 4이상이면(사이클이 형성되기 위해선 지나간 점들이 최소 4개 이상이어야함) result에 값을 넣어주고 return 해준다. 그 이후엔 result가 값이 있으면 yes를 출력하고 없으면 no를 출력해준다.

import sys
input=sys.stdin.readline
n,m = map(int,input().split())
ary = [list(input()) for _ in range(n)]
dx=[1,0,0,-1]
dy=[0,1,-1,0]
visited = [[0 for _ in range(m)] for __ in range(n)]
result=[]
def dfs(x,y,prex,prey,cnt):
    if visited[x][y] and cnt >=4:
        result.append("yes")
        return
    visited[x][y]=1
    for idx in range(4):
        nx = dx[idx]+x
        ny = dy[idx]+y
        if 0<=nx<n and 0<=ny<m and ary[nx][ny]==ary[x][y]:
            if [nx,ny]!=[prex,prey]:
                dfs(nx,ny,x,y,cnt+1)


for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            dfs(i,j,i,j,0)
if result:
    print("Yes")
else:
    print("No")