[백준 / Python] 16929번 Two Dots | 초코더

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

16929번: Two Dots

접근법

DFS로 탐색하면서 사이클이 있는지 확인했습니다. 사이클의 여부는 선분의 길이가 최소선분 길이인 4이상이면서 시작좌표와 끝좌표가 같으면 사이클이 있다고 하였습니다.

 

DFS함수를 살펴보겠습니다.

dfs(x,y,cnt,color,sx,sy)

x,y는 현재좌표, cnt는 선분의길이, color는 점의색, sx,sy는 첫시작좌표입니다.

1. 범위가 넘어가는지 확인해줌

2. cnt가 4이상이면서 첫시작좌표와 탐색중인좌표가 같으면 True를 리턴

3. 탐색중인 좌표가 방문하지 않은 곳이면서 탐색중인 좌표의 색이 시작좌표의 색과 같으면 -> dfs재귀호출(cnt를 증가시키고!)

나의풀이

import sys

n,m=map(int,input().split())
game=[[p for p in sys.stdin.readline().strip()] for _ in range(n)]
visited=[[0]*m for _ in range(n)]
dx=[-1,0,1,0]
dy=[0,1,0,-1]

ans=False
def dfs(x,y,cnt,color,sx,sy):
    global ans

    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        #사이클을 하나 찾으면 종료시키기
        if ans is True:
            return
        if nx>=n or nx<0 or ny>=m or ny<0:
            continue
        #최소한의 사이클인 4이상이면서 첫번째좌표와 현재좌표가 같으면 True
        if cnt>=4 and sx==nx and sy==ny:
            ans=True
            return True
        if visited[nx][ny]==0 and game[nx][ny]==color:
            visited[nx][ny]=1
            dfs(nx,ny,cnt+1,color,sx,sy)
            visited[nx][ny]=0
    return False


def solve():
    global ans
    for i in range(n):
        for j in range(m):
            sx=i
            sy=j
            visited[sx][sy]=True
            dfs(i,j,1,game[i][j],sx,sy)
            if ans:
                return 'Yes'
    return 'No'
print(solve())