[알고리즘] DFS - 경로탐색

https://lovenewthing.tistory.com/88 이 문제랑 비슷해보이지만 다르다. 푸는 원리는 같다. 그러나 문제에서 원하는 바가 무엇이냐에 따라 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줄에 걸쳐 연 결정보가 주어진다.

 

▣ 출력설명

총 가지수를 출력한다.

 

▣ 입력예제

5 9

1 2

1 3

1 4

2 1

2 3

2 5

3 4

4 2

4 5

 

▣ 출력예제

6

 

풀이

def DFS(L):
    global cnt
    if L == n:
        cnt += 1
        # print(stack)
    else:
        for i in range(1, n+1):
            if g[L][i] == 1 and ch[i] == 0:
                ch[i] = 1
                # stack.append(i)
                DFS(i)
                # stack.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
    ch[1] = 1
    stack = [1]
    DFS(1)
    print(cnt)

주석처리한 stack값을 출력해보면 다음처럼 경로가 찍히는 것을 볼 수 있다. 주석처리한 부분이 있든없든 코드는 똑같이 실행되지만, 출력을 찍어보면 경로가 어떤식으로 돌아가는지 이해할 수 있다.

[1, 2, 3, 4, 5]
[1, 2, 5]
[1, 3, 4, 2, 5]
[1, 3, 4, 5]
[1, 4, 2, 5]
[1, 4, 5]

 

1. 먼저 입력받고 그래프배열과 체크배열을 만들 때, 1번부터 시작할때 직관적으로 이해하고, 입력받을때 그래프를 더 그리기 쉽게 하도록 초기화할때 길이를 n+1까지 반복하여서 인덱스가 n까지 가능하도록 해주었다.

 

2. 항상 1번노드부터 시작하니까, stack에다가 1을 넣어준다. 그리고 체크배열에 1번인덱스에도 체크해줌

 

3. 그래프 배열에서 [1][c]에 1이 있고, 체크배열에 체크가 안됐으면 DFS()에 c를 넣고 그 c에서 다시 줄기를 뻗어나간다.

 

4. 그렇게 줄기를 이어가다가 DFS()에 인자로 넣는 값이 n이면 도착!!!인거니까 cnt를 하나 늘려주는 식임.

 

5. n에 도착하든 안하든 일단 그과정에서 DFS가 마무리 되면 해당줄로 돌아와서 ch해제하는 것도 잊으면 안됨.

예를 들어, 3-1-5 루트를 통해 5에 도착했고, 이제 3-2-ㅁ로 옮겨갈거면, 5의 체크와 1의 체크를 해제해야 한다. dfs(1)이 5까지 다 돌고 끝난거니까.