[dfs/백준] 16929번 : Two Dots

- 문제 : https://www.acmicpc.net/problem/16929

 

Gold Level4 문제 

같은 색인 점을 탐색하다가 그것이 사이클을 이루는 경우는 Yes, 아닌 경우는 No를 출력하는 문제였다

탐색하는 건 괜찮은데, 여전히 사이클을 이루는지 확인하는 것에서 막혔다 

 

사이클이 되는 조건은 시작 점에 다시 도착하는 것이고, 지나온 점의 갯수가 4개 이상이 되는 것이다.

시작하는 점과 지나온 점의 갯수를 파라미터에 넣어서 같이 탐색 돌리면 된다 

 

각 점마다 visit도 초기화하고, 각 점을 시작으로 사이클을 찾는 방법인 것 같다 

 

- 정답 풀이 :

n,m = map(int,input().split())
data = []
dx = [-1,1,0,0]
dy = [0,0,-1,1]

for _ in range(n):
    data.append(list(input()))

def dfs(x,y,letter,count,sx,sy):
    global flag
    for i in range(4):
        nx,ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if not visit[nx][ny] and data[nx][ny] == letter:
                visit[nx][ny] = 1
                dfs(nx,ny,letter,count+1,sx,sy)
            elif count >= 4 and sx == nx and sy == ny:
                flag = True
                return          
                
flag = False                                               
for i in range(n):
    for j in range(m):
        sx,sy=i,j
        visit = [[0]*m for _ in range(n)]
        visit[sx][sy] = 1
        dfs(i,j,data[i][j],1,sx,sy)
        if flag:
            print('Yes')
            exit()
        
if not flag:
    print('No')