57)경로 탐색(그래프 DFS)

문제

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하기

 

조건

아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 

총 6 가지입니다.

 

그래프에서 경로란 방문한 노드는 중복해서 방문하지 않습니다.

 

제한사항

첫째 줄에는 정점의 수 N(2<=N<=20)와 간선의 수 M가 주어진다.

 

그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.

 

총 가지수를 출력한다.

 

문제풀이

def go(v):
  global cnt

  if v==N:
    cnt+=1
    for x in path:
      print(x, end=' ')
    print()
    
  else:
    for i in range(1, N+1):
      if g[v][i]==1 and ch[i]==0:
        ch[i]=1
        path.append(i)
        go(i)
        ch[i]=0
        path.pop()

N, M=map(int, input().split())
g=[[0]*(N+1) for _ in range(N+1)]
ch=[0]*(N+1)
for i in range(M):
  a, b=map(int, input().split())
  g[a][b]=1
cnt=0
path=[]
path.append(1)
ch[1]=1
go(1)
print(cnt)