[인프런] 경로 탐색

---

문제설명

방향그래프가 주엊면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성해라. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지이다.

 

입력조건

• 첫 줄에는 정점의 수 N(2 <= N <=20)과 간선의 수 M이 주어진다. 그 다음부터 M줄에 걸쳐 연결정보가 주어진다.

출력조건

• 총 가지수를 출력한다.

사고과정

• 주어지는 그래프 정보를 나는 인접리스트 형태로 저장한 후 이를 DFS로 탐색하면서 경로 수를 셋다. 단, 한 갈래를 계속 탐색하면서 방문한 노드는 체크해주는 방문 체크용 테이블을 하나 정의해주어야 한다. 그리고 백트래킹 시 방문했던 노드의 값을 다시 0으로 바꾸어주어야 한다! 도착 노드도 마찬가지!
• DFS 함수에 인자를 Level, node 2개로 주었는데, L이 없어도 테스트 케이스에는 무사통과되었다. L을 넣은 이유는 혹시나 계속 재귀적으로 탐색하는 게 있을 까봐 그랬는데, 사실상 방문용 테이블에서 체크를 해주기 때문에 빼주어도 상관은 없을 듯하다.
• 풀이를 보니 강사님께서는 주어진 그래프 데이터를 인접행렬 형태로 저장한 후 수행하셨다. 나머지 로직은 나의 풀이와 동일!

풀이

- 나의 풀이(인접리스트로 저장)

n, m = map(int, input().split())
graph = [[] * (n+1) for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

visited = [0] * (n+1)
visited[1] = 1  # 시작노드 방문처리
cnt = 0

def dfs(node):
    global cnt
    if node == n:  # n번 정점까지 가는 길 있음
        cnt += 1
        visited[n] = 0  # 도착 노드 방문처리 다시 초기화 -> 그래야 다른 경로 탐색시 밑 else 구문의 if visited[next] == 0 통과할 수 있음
        return
    else:
        for next in graph[node]:
            if visited[next] == 0:
                visited[next] = 1
                dfs(next)
                visited[next] = 0

dfs(node=1)
print(cnt)

- 강의 풀이(인접행렬로 저장)

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  # 시작노드 방문처리

def DFS(v):
    global cnt
    if v == n:
        cnt += 1
        for p in path:
            print(p, 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)
                ch[i] = 0
                path.pop()  # 백할 때 경로도 빼주어야 함!


DFS(1)
print(cnt)