경로 탐색

방향그래프가 주어지면 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(node):
    global cnt
    if node == N:
        cnt += 1
    else:
        for next in range(2,N+1):
            if matrix[node][next] == 1 and dup_check[next] == 0:
                dup_check[next] = 1
                DFS(next)
                dup_check[next] = 0

if __name__=="__main__":
    N,M = map(int, input().split())
    matrix = [[0 for _ in range(N+1)] for _ in range(N+1)]
    for i in range(M):
        start, end = map(int, input().split())
        matrix[start][end] = 1
    dup_check = [0]*(N+1)
    cnt = 0
    DFS(1)
    print(cnt)

 

모범답안

#모범답안
import sys
sys.stdin = open("input.txt",'rt')
def DFS(v):
    global cnt, path
    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
    ch[1] = 1
    path = list()
    path.append(1)
    DFS(1)
    print(cnt)

 

느낀점

1. 우선 수월하게 풀었당.
DFS의 매개변수를 꼭 트리의 레벨로 할 필요는 없다는 점을 융통성있게 아주 잘 생각해냈당!
자만하지말고 모범답안 보면서 꾸준히 리뷰하장.

2. 1에서 출발하는게 fix니까 다시 1로 갈 일은 없기때문에
가지 반복문을 2부터 시작하면서 구현했는데,
좀 더 명확한 방법은 아무래도 모범답안이려나?! 그래도 난 내 사고방식도 맘에든다.

3. 문제는 경로의 경우의 수만 구하면되기 때문에 굳이 path를 저장하지 않았는데,
모범답안은 연습겸 경로 출력까지 구현한듯 하다.
path 리스트를 매번 초기화하는것보다, 하나씩 넣고 빼면서 구현하는 방법이
참 좋은것같다! 다음에 분명 쓸일이 있을 테니 명심해야징.

4. 다시 풀기는 나도 경로 출력까지 해봐야겠당.

---

다시 풀어보기

#다시
import sys
sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline

def DFS(v):
    global cnt, path
    if v == N:
        cnt += 1
        for x in path:
            print(x, end=' ')
        print()
    else:
        for next in range(1,N+1):
            if matrix[v][next] == 1 and dup_check[next] == 0:
                dup_check[next] = 1
                path.append(next)
                DFS(next)
                dup_check[next] = 0
                path.pop()


if __name__ == "__main__":
    N, M = map(int, input().split())
    matrix = [[0 for _ in range(N+1)] for _ in range(N+1)]
    for _ in range(M):
        start, end = map(int, input().split())
        matrix[start][end] = 1
    dup_check = [0]*(N+1)
    cnt = 0

    dup_check[1] = 1
    path = [1]
    DFS(1)
    print(cnt)