경로 탐색(그래프 DFS : Depth First Search) python

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

---

풀이

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

if __name__=="__main__":
    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)
    ch[1]=1
    cnt=0
    path=[]
    path.append(1)
    DFS(1)
    print(cnt)

-행렬 생성

g=[[0]*(n+1) for _ in range(n+1)]

    for i in range(m):

        a,b=map(int,input().split())

        g[a][b]=1

이동 가능한 부분을 1로 표시하여 행렬 작성

 

-체크 리스트 생성-->중복 방지

ch=[0]*(n+1)

    ch[1]=1

이미 갔던 노드는 가면 안된다는 조건이 있으므로 체크 리스트를 생성한다

 

-DFS

else:

        for i in range(1,n+1):

            if g[s][i]==1 and ch[i]==0:

                ch[i]=1

                path.append(i)

                DFS(i)

                path.pop()

                ch[i]=0

g[s][i]==1인 경우에 이동이 가능하고 중복되면 안되므로 ch[i]==0일 때 다음 코드들을 처리한다.

path리스트는 이동한 흔적을 담는 리스트이다.

DFS(i)가 실행되고 나서 생긴 값들은 다시 초기화 되어야 하므로

path.pop()

ch[i]=0

두 줄의 코드를 작성한다.

 

-경로 완결시 (if s==n일 때)

경로의 개수를 세는 것이 문제이므로 cnt에 1을 더하고 코드가 끝났을 때의 cnt값을 출력한다.