[Python Algorithm] 완전탐색(DFS) - 경로 탐색(그래프 DFS)

> 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / DFS 기초 

 

 

 

📖 문제 : 경로 탐색 (그래프 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

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

n, m = map(int, input())
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
DFS(1)
print(cnt)

 

 

⭐️ Point ! ⭐️

• 재방문은 못함
  
  
• back 할 때 check를 해제해주어야 함.
  
  
• 위에서는 인덱스 0번은 사용하지 않음.
• 주석처리 된 것은 루트 출력을 위한 코드
  
  
•  이런 식으로 !

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이