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

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[경로 탐색(그래프 DFS)]

 

방향 그래프가 주어지면 1번 노드에서 N번 노드로 가는 모든 경우의 수를 출력하는 프로그램을 작성하시오.

예를 들면, 아래 방향 그래프의 1번 노드에서 5번 노드로 가는 모든 경우의 수는 6가지이다.

 

방향 그래프

모든 경우의 수

 

 

*입력 설명

첫 번째 줄에는 노드의 수 N(2 ≤ N ≤ 20)과 간선의 수 M이 주어진다.

그 다음부터 M줄에 걸쳐 노드 간의 연결 정보가 주어진다.

 

*출력 설명

첫 번째 줄부터 모든 경우의 수의 경로를 출력한다.

마지막 줄에는 모든 경우의 수를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_55.txt', 'rt')

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):
            if g[v][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)]
    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)
    
'''
출력 :
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

'''

 

input_55.txt(입력)

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

 

 

중요내용

1. DFS() 함수의 인자 v와 for문의 i는 그래프의 노드 번호를 의미한다.
2. 참고로, v는 출발지점의 노드 번호를 의미하고 i는 도착지점의 노드 번호를 의미한다. (ex. g[1][2] == 1은 1번 노드에서 2번 노드로 이동할 수 있음을 의미함)
3. 변수 ch는 체크변수이며, 한 번 방문한 노드를 재방문하지 않기 위해 사용된다. (ch[0] == 0 : 미방문, ch[1] == 1 : 방문)
4. 참고로, 변수 cnt로 경우의 수를 카운트하면 그 이후에는 체크변수 ch의 값을 0으로 모두 초기화시켜야 한다. (ex. ch[i] = 0)
5. 2차원 리스트 g와 체크변수 ch의 원소 개수를 모두 n+1개로 만든 것은 1~n번 까지의 노드를 고려해야 하기 위함이다.
6. 변수 path는 모든 경우의 수의 경로를 저장하는 리스트로 사용된다.