[파이썬 알고리즘 문제풀이] - Section6 / 완전탐색 (백트랙킹, 상태트리와 CUT EDGE)-DFS(깊이우선탐색)기초 - 12

⚽ 경로 탐색(그래프 DFS)

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

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

총 6 가지입니다.
그래프에서 경로란 방문한 노느는 중복해서 방문하지 않습니다.

▣ 입력설명
첫째 줄에는 정점의 수 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

import sys
sys.stdin = open("input.text", "rt")

n, m = map(int, input().split())
g = [[0] * (n+1) for _ in range(n+1)]
for i in range(m):
    a,b = map(int, input().split())
    g[a][b] = 1

    
ch = [0] * (n+1) #중복 체크리스트
cnt = 0
path = []
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): #1~n번 노드까지 있잖아. 개수만큼 가지 뻗어서 확인해야지
            if g[v][i] == 1 and ch[i] == 0: #해당 i 인접노드가 연결되어 있고 방문 전이라면
                ch[i] = 1
                path.append(i)
                DFS(i)
                path.pop() #백할 때는 경로에서 지워줘야지
                ch[i] = 0 #백 트랙킹 이후 방문 표시 없애야지

ch[1] = 1 #시작은 1번노드니까 1번 방문 표시 하고 들어가야지
path.append(1) #시작 지점 경로에 넣고..
DFS(1)
print(cnt)

코멘트

가중치 방향 그래프 + DFS. 이제 그래프를 활용해 나갈 것인데 방문을 인접 노드 방문 했는지 안했는지 등을 확인해 나갈거야. 위 코드와 비슷한 문제들 매우 많을 거니까 문제 느낌 이해하기