[백준/dfs] 16929번: Two Dots

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

 

사이클 있는지 여부를 구하는 문제이다. 

이전에 사이클 관련 문제를 푼 적이 있기에 cycle이라는 리스트를 선언해서 이동할 때 방문하지 않았고, 사이클 문자와 동일한 경우만 cycle리스트에 삽입해준 후 이동하다 문자가 cycle에 있는 문자와 같을 경우 True를 선언하고 함수를 종료하는 거라고 생각했다. 생각해보니 cycle에는 이미 같은 문자들만 들어가있다;; 이부분 주의하기!!

 

그러니 문제에서 말한대로 처음 좌표와 들어온 값의 좌표가 같고, 크기가 4이상인 경우 사이클이라고 간주해 flag=True를 하고 반환하면 된다.

매 dfs를 실행할 때마다 visit 행렬을 초기화해준다 

 

-정답풀이: 

n,m=map(int,input().split())
s=[list(input()) for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
visit=[[0]*m for _ in range(n)]

def dfs(x,y,word,cnt,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:
            #사이클 길이 4이상이면서, 첫번째 좌표가 현재 좌표가 같으면 True
            if cnt>=4 and sx==nx and sy==ny: ###
                flag=True
                return
            if not visit[nx][ny] and s[nx][ny]==word:
                visit[nx][ny]=1
                dfs(nx,ny,word,cnt+1,sx,sy)
                
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,s[i][j],1,sx,sy)
        if flag:
            print("Yes")
            exit()
        
if not flag:
    print("No")

 

-틀린 풀이: 

메모리초과,RecursionError가 다 났던 코드,,

n,m=map(int,input().split())
s=[list(input()) for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
visit=[[0]*m for _ in range(n)]

def dfs(x,y,word):
    visit[x][y]=1
    global flag
    cycle.append(s[x][y])
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m:
            if visit[nx][ny] and s[nx][ny]==word:
                if s[nx][ny] in cycle:
                    flag=True
                    return
            else:
                dfs(nx,ny,word)
flag=False
for i in range(n):
    for j in range(m):
        if not visit[i][j]:
            cycle=[]
            dfs(i,j,s[i][j])
            if flag:
                print("Yes")
                exit()
if not flag:
    print("No")