16929번 Two Dots 백준 파이썬

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

16929번: Two Dots

 

 

N,M=map(int,input().split())
arr=[list(map(str,input()))for _ in range(N)]
visited = [[False]*M for _ in range(N)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
flag=False
def scope(y,x):
    if y>=0 and y<N and x>=0 and x<M:
        return True
    else:
        return False
 
def dfs(y,x,py,px,ball):
    if visited[y][x]==1:
        return True
    visited[y][x]=True
 
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if ny!=py or nx!=px:
            if scope(ny,nx) and arr[ny][nx]==ball :
                if dfs(ny,nx,y,x,ball): 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 print("No")

참고:https://shinbian11.tistory.com/60

[백준] 16929번 : Two Dots

위의 그림은 싸이클이 있는 경우와 없는 경우의 예를 보여준다.

싸이클이 있는 경우에는 방문한 적 있는 점을 다시 만날 경우가 싸이클이 존재하는 경우이다.

단 바로 이전의 점을 방문할 우려가 있어서 if ny!=py or nx!=px: 라는 조건문을 걸어 주었다.

그러면 ny==py and nx==px 인 경우를 제외하고 주변의 모든 점을 깊이 우선 순회를 할 수 있기 때문이다.

        if dfs(i,j,0,0,arr[i][j]):
            flag=True
            break    
print("Yes") if flag else print("No")

그리고 싸이클 존재유무만 알면 되므로 싸이클이 존재하면 flag=True로 두고 반복문을 나간다.

싸이클 존재 유무에 따른 결과값을 출력하면 된다.