파이썬 백준 16724 피리부는 사나이

문제)

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

16724번: 피리 부는 사나이

 

소스코드)

import sys
sys.setrecursionlimit(10**8)
n, m = map(int, input().split())
dirmap = [sys.stdin.readline().rstrip() for _ in range(n)]
#print(dirmap)
visited = [[False] * m for _ in range(n)]
finished = [[False] * m for _ in range(n)]
cnt = 0
#cycle, join in the middle of the cycle, not ~~

def dfs(i, j, dir):
    global cnt
    if visited[i][j] and finished[i][j] == False:
        cnt += 1
        #print(i, j, cnt)
        return
    if finished[i][j]:
        finished[i][j] = True
        return

    visited[i][j] = True

    if dir == "D":
        dirtemp = dirmap[i+1][j]
        #print(dir, i, j)
        dfs(i+1, j, dirtemp)
        finished[i][j] = True

    elif dir == "U":
        dirtemp = dirmap[i-1][j]
        #print(dir, i, j)
        dfs(i-1, j, dirtemp)
        finished[i][j] = True

    elif dir == "R":
        dirtemp = dirmap[i][j+1]
        ##print(dir, i, j)
        dfs(i, j+1, dirtemp)
        finished[i][j] = True

    elif dir == "L":
        dirtemp = dirmap[i][j-1]
        #print(dir, i, j)
        dfs(i, j-1, dirtemp)
        finished[i][j] = True


for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            a = dirmap[i][j]
            dfs(i, j, a)

#print(visited)
#print(finished)
print(cnt)

 

이 방법은 방향그래프에서 사이클을 찾는 방법이다.

구글에 16724번을 검색해보니 많은 사람들이 union-find로 풀었고 나처럼 finished 변수를 하나 더 만들어

백엣지가 존재하는 지 살피는 코드는 보이지 않아 글을 쓰게 됐다.

이 방법은 재귀로 쭉 내려가다가 이미 방문했는데 사이클이 만들어지진 않은 곳에 탐색이 들어가면 함수를 return

시켜준다. 이미 방문한 곳인데 finished가 false라는 건 시작 정점에서 다시 시작 정점으로 온 것이기 때문이다.

그렇게되면 사이클을 하나 찾은 것이다.

 

제출을 하다가 메모리초과하는 부분이 있었다. 이미 visited가 true이고 finished가 true인 즉, 이미 방문했던 사이클을 다시 방문하는 경우가 생길경우 계속 재귀 탐색을 하게 되면서 메모리초과를 하게 된 것이다.

예를 들어,

R R R D

U U U L

여기서, RRRDLU 이 부분을 이미 방문했을 경우 저 밑에 코드가 없다면 계속 재귀 탐색을 하게 되더라.

 

그 부분을 

if finished[i][j]:
    finished[i][j] = True
    return

이미 방문했던 사이클이면 바로 함수를 끝내게 해주었다.

 

UNION-FIND 알고리즘도 공부를 해봐야 할 것 같다.