16929번: Two Dots (DFS, 사이클 판단)

16929번: Two Dots

같은 색으로 이루어진 사이클을 찾는 과정은 간단하다. 같은 색으로 이루어진 공간만을 이동하면서 탐색을 진행하는데 만약 이동하려는 공간이 바로 전 depth에서 탐색한 노드가 아니고(다시 돌아가는 경우) 이전에 방문했었더라면 사이클을 만들 수 있다.

---

아래 코드에서 recur[]은 탐색하고자 하는 색에서 방문할 때마다 현재의 탐색깊이를 저장한 것이며 recur를 통해 이전에 방문했는지, 바로 이전에 탐색한 곳인지를 확인하고 모든 칸에서 DFS를 진행하는 방식으로 사이클이 존재하는지 판단하고 만약 존재하지 않으면 No를 출력하도록 했다. 

 

n,m = map(int,input().split())
dx = [1,-1,0,0]
dy = [0,0,-1,1]
graph = []
for i in range(n):
    graph.append(input())
visited = [[False for i in range(m)] for j in range(n)]
def dfs(x,y,recur,depth):
    visited[x][y] = True
    recur[x][y] = depth
    for i in range(4):
        nx = x+dx[i]
        ny = y +dy[i]
        if nx<0 or nx>=n or ny<0 or ny>=m:
            continue
        if recur[nx][ny] !=0 and recur[nx][ny] != depth-1:
            print('Yes')
            exit()
        if graph[nx][ny] == graph[x][y] and recur[nx][ny]==0:
            dfs(nx,ny,recur,depth+1)
    recur[x][y] = 0

for i in range(n):
    for j in range(m):
        recur = [[0 for _ in range(m)] for _ in range(n)]
        dfs(i,j,recur,1)
print('No')

맞긴했지만 모든 칸에서 dfs를 하는 것은 시간적으로 손해라고 생각해서 visited를 도입해 이미 탐색한 공간이라면 dfs를 진행하지 않는 방식으로 코드를 작성해보았고 미세하나마 4ms 정도 빨랐다. 

n,m = map(int,input().split())
dx = [1,-1,0,0]
dy = [0,0,-1,1]
graph = []
for i in range(n):
    graph.append(input())
visited = [[False for i in range(m)] for j in range(n)]
def dfs(x,y,recur,depth):
    visited[x][y] = True
    recur[x][y] = depth
    for i in range(4):
        nx = x+dx[i]
        ny = y +dy[i]
        if nx<0 or nx>=n or ny<0 or ny>=m:
            continue
        if recur[nx][ny] !=0 and recur[nx][ny] != depth-1:
            print('Yes')
            exit()
        if graph[nx][ny] == graph[x][y] and visited[nx][ny]==False:
            dfs(nx,ny,recur,depth+1)
    recur[x][y] = 0

for i in range(n):
    for j in range(m):
        recur = [[0 for _ in range(m)] for _ in range(n)]
        dfs(i,j,recur,1)
print('No')