경로 탐색(그래프 DFS)

문제

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

참고) 경로란? 방문한 노드는 중복해서 방문하지 않는다.

입력

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

출력

6

생각 포인트

• 한번 방문한 노드는 다시 방문하면 안되기에 방문한 노드를 check 할 check list를 사용하자.
• 1번 노드부터 시작할것이니 dfs(1)로 시작하면서 check list에 1번을 check
• 인접행렬은 옆으로 갈 수 있지만 check list를 확인하여 check 되어 있으면 가지 않는다.
• 백트래킹을 할 땐 다시 check를 풀어주어야 한다.

Solution

n, m = map(int, input().split())
graph = [[0] * (n+1) for _ in range(n+1)]
# path = []  # 경로까지 출력하기 위해 선언. 문제만 푸는데는 필수적이지 않음.
check = [0] * (n+1)
check[1] = 1
# path.append(1)
cnt = 0

for _ in range(m):
    row, col = map(int, input().split())
    graph[row][col] = 1

def dfs(v):
    global cnt
    if v == n:
        cnt += 1
        # for x in path:
        #     print(x, end=' ')
        # print()
    else:
        for i in range(1, n+1):
            # v번째 노드에서 i번째 인덱스로 갈 수 있다면 graph[v][i] = 1
            if graph[v][i] == 1 and check[i] == 0:
                check[i] = 1
                # path.append(i)
                dfs(i)
                # back 하는 지점. check 풀어주기.
                check[i] = 0
                # path.pop()

dfs(1)
print(cnt)