[Algorithms] 완전탐색(백트랙킹, 상태트리와 CUT EDGE)/깊이우선탐색(DFS) Basic-경로 탐색(그래프 DFS)

 

• 중복해서 방문하지 않는다는 것에서 check list를 떠올리자 
• 1번 vertext에서 갈 수 있는 길이 5가지 가짓수가 있고 그 중에 방향그래프로 연결된 다음 vertext로 이동하면 된다 

 

def DFS(vertex):
    global cnt
    if vertex == n:
        cnt += 1
    else:
        for i in range(1, n+1):
            if ch_ls[i]==0 and arr[vertex][i]==1:
                ch_ls[i]=1
                DFS(i)
                ch_ls[i]=0
 
if __name__ == '__main__':
    n, m = map(int, input().split())
    arr = [[0]*(n+1) for _ in range(n+1)]
    cnt = 0
    ch_ls = [0] * (n+1)
    for _ in range(m):
        i, j = map(int, input().split())
        arr[i][j]=1
    ch_ls[1]=1        # vertext 1에서 출발하니까 체크해놓고 시작한다!!
    DFS(1)
    print(cnt)