DFS로 사이클 탐지하는 알고리즘 탐구하기2 -사이클의 길이-

1. 연습문제1

 

9466번: 텀 프로젝트 (acmicpc.net)

 

문제를 보면 u가 A[u]를 향하는 그래프이고 이 그래프에서 사이클을 모두 찾아 각 사이클에 속하는 노드의 개수를 구하고

 

전체 노드 수에서 사이클에 속하는 노드의 개수를 빼면 된다

 

dfs로 사이클을 탐지할 수는 있는데... 사이클에 속하는 노드의 개수는 어떻게 알 수 있을까?

 

노드 u1부터 u2,u3,...,un을 차례대로 방문한다고 생각해보자

 

u1 > u2 > u3 > .... > un

 

그러다가 다시 un에서 u1으로 온다면?

 

u1 > u2 > u3 > ... > un > u1으로 오면 (u1,u2,.u3,...,un)이 하나의 사이클이 된다.

 

따라서 dfs로 노드를 방문할때마다, 방문한 노드의 번호를 1,2,3,.. 순서대로 매겨준다.

 

현재 u에서 A[u]로 이동했더니, 사이클이 탐지되었다면...

 

u의 번호와 A[u]의 번호 차이에 1을 더하면 사이클의 크기가 된다.

 

 

마지막에 도달한 A[u]의 숫자가 더 크니까, A[u]의 번호에 u의 번호의 차이 + 1을 해야하는거 아닌가?

 

라고 생각했는데

 

예를 들어 다음과 같은 그래프를 보자

 

 

 

 

1번부터 시작해서 7번까지 순회하여 dfs를 수행하여 사이클을 찾을 건데

 

1번에는 1을 표시하고 다음 3번으로 간다

 

 

 

 

그러면 3번에서는 2로 표시하고 다음 3번으로 이동

 

그러면 3번으로 오면서 사이클이 탐지될거고, 3번에 표시된 숫자 2와 3번에 표시된 숫자 2의 차이 + 1 = 1이 사이클의 길이

 

그리고 dfs가 끝나면서 아직 방문하지 않은 2번을 방문할것

 

2번에는 1을 표시하고 1번으로 이동하는데, 이미 방문이 끝났으니까 종료

 

 

 

이제 4번을 방문할 차례인데, 4번에는 1을 표시

 

다음 7번에는 2를 표시, 6번에는 3을 표시하게 된다.

 

 

 

 

그러면 6번 노드에서 4번 노드로 이동하는데, 사이클이 탐지되었다.

 

u = 6이고 A[u] = 4이며, u = 6에 표시된 숫자는 3이고 A[u] = 4에 표시된 숫자는 1이다.

 

따라서 이 사이클의 길이는 3 - 1 + 1 = 3이 된다

 

from sys import stdin,setrecursionlimit
setrecursionlimit(10**5)

def dfs(u,order):
    
    global count

    if visited[u]:
        
        if visited[u] == -1:

            return True
        
        return False
    
    visited[u] = -1
    
    #u에 order을 표시하고,
    ordering[u] = order
    
    #다음 A[u]-1로 이동(zero index)
    if dfs(A[u]-1,order+1):
        
        #사이클이 탐지되었다면, u~A[u]까지 사이클이고
        #u와 A[u]에 표시된 번호 차이에 1을 더한 것이 사이클의 길이
        count += (ordering[u] - ordering[A[u]-1]+1)

    visited[u] = 1
    
T = int(stdin.readline())

for _ in range(T):
    
    n = int(stdin.readline())

    A = list(map(int,stdin.readline().split()))

    visited = [0]*(n+1)
    ordering = [0]*(n+1)

    count = 0

    for i in range(n):

        if visited[i] == 0:

            dfs(i,1)
    
    print(n - count)

 

 

 

2. 실제 사이클을 찾는 방법

 

사실 코드만 보면... 직관적이지 않다

 

사이클이 뭔지 다시 생각해보면 

 

노드 u1부터 u2,u3,...,un을 차례대로 방문한다고 생각해보자

 

u1 > u2 > u3 > .... > un

 

그러다가 다시 un에서 u1으로 온다면?

 

u1 > u2 > u3 > ... > un > u1으로 오면 (u1,u2,.u3,...,un)이 하나의 사이클이 된다.

 

u1에서 dfs를 시작한다고 할때,

 

u1 > u2 > u3 > u4 > u5 > ... > un까지 잘 왔는데, un > u4로 이동한다고 해보자.

 

그러면 u4 > u5 > ... > un > u4가 하나의 사이클을 형성한다.

 

 

따라서 u1에서 dfs를 수행하면서, 이동한 노드 번호를 리스트에 저장한 다음...

 

u에 왔는데 사이클이 탐지된 순간 해당 노드 u가 리스트의 어디 인덱스에 있는지 찾아내고...

 

그 인덱스부터 리스트의 끝까지가 하나의 사이클이 된다

 

 

def dfs(u,path):
    
    global count

    if visited[u]:
        
        if visited[u] == -1:
            
            #u로 왔는데, 사이클이 탐지되었다
            
            #그동안 저장된 path는 도달한 노드를 순서대로 
            #u > u1 > u2 > .... > un이 저장되어 있다
            
            #path를 차례대로 순회해서 u의 위치를 알아낸다.
            
            #[u1,u2,u3,...,un]에서 j번이 u라면...
         
            #path[j:]가 사이클이다
            
            for j in range(len(path)):
                
                if path[j] == u:

                    break

            count += (len(path) - j)

            return True
        
        return False
    
    visited[u] = -1
    
    #도달한 노드 u를 path에 저장
    path.append(u)
    
    #다음 노드 A[u]로 이동
    dfs(A[u]-1,path)
    
    visited[u] = 1

 

 

 

 

 

여기서 보면 1번부터 시작해서, path = [1,3] 저장되어있는데 3에 온 순간 사이클이 탐지되어서 

 

path에서 3을 찾으면 1번이니까, path[1:] = [3]이 하나의 사이클이다

 

다시 4번부터 시작하면 [4,7,6]을 방문하다가 4번을 방문할려하면 사이클이 탐지되는데

 

4번은 path에 0번에 있으니까 path[0:] = [4,7,6]이 하나의 사이클이다

 

실제로 속도도 그렇게 차이나지 않고 로직이나 코드가 조금 더 알아보기 쉽다고 해야하나?

 

이것보다 더 빠른 방법을 알게된다면..

 

나중에 기록할 기회가 있겠지