055 - 경로 탐색(그래프 DFS)

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

 

 

아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 아래와 같이 6 가지 입니다.

1 2 3 4 5 
1 3 4 2 5
1 3 4 5

 

1 4 2 5

1 4 5

 

 

▣ 입력설명
첫째 줄에는 정점의 수 N(2<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.

 

▣ 출력설명
총 가지수를 출력한다.

 

▣ 입력예제 1

5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

 

▣ 출력예제 1

6

 

 

 

def DFS(L):
    global step, cnt

    if L >= n:
        cnt += 1
        print('cnt:{}, step:{}'.format(cnt, step)) # 라우팅 디버깅용
        return
    else:
        for i in range(1, n+1):
            if ch[i] == 0 and g[L][i] == 1:
                ch[i] = i
                step.append(i)  # 라우팅 디버깅용
                DFS(i) # 핵심은 레벨탐색 처럼하지만 숫자를 직접 넘긴다
                step.pop()  # 라우팅 디버깅용
                ch[i] = 0


if __name__ == '__main__':
    n, m = map(int, input().split())
    g = [[0]*(n+1) for i in range(n+1)]
    ch = [0]*(n+1)
    cnt = 0
    step = []  # 라우팅 디버깅용
    for i in range(m):
        a, b = (map(int, input().split()))
        g[a][b] = 1
    ch[1] = 1
    step.append(1)  # 라우팅 디버깅용
    DFS(1)
    print(cnt)