[Algorithm] 경로탐색 (그래프 DFS) (두 가지 방법)

⭐ 방문 체크를 풀어줘야 되돌아간 후 다시 사용 가능

방법1) graph 변수에 연결된 노드만 담기

import sys
sys.stdin = open("input.txt", "rt")
input = sys.stdin.readline

def DFS(start):
    global cnt

    visited[start] = 1

    if start == n:
        cnt += 1
    else:
        for i in graph[start]:
            if visited[i] == 0:
                visited[i] = 1
                DFS(i)
                visited[i] = 0  # 체크 풀기!
    return cnt

if __name__ == '__main__':
    n, m = map(int, input().split())

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

결과

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

---

방법2) 인접행렬로 만들기

import sys
sys.stdin = open("input.txt", "rt")
input = sys.stdin.readline

def DFS(v):
    global cnt
    global res

    if v == n:
        cnt += 1
        for x in res:
            print(x, end=' ')
        print()

    else:
        for i in range(1, n+1):
            if graph[v][i] == 1 and visited[i] == 0:
                res.append(i)
                visited[i] = 1
                DFS(i)
                visited[i] = 0
                res.pop()

if __name__ == '__main__':
    n, m = map(int, input().split())

    graph = [[0]*(n+1) for _ in range(n+1)]
    visited = [0]*(n+1)
    for i in range(m):
        a, b = map(int, input().split())
        graph[a][b] = 1
    print(graph)
    cnt = 0
    visited[1] = 1
    res = []
    res.append(1)
    DFS(1)
    print(cnt)

결과

[[0, 0, 0, 0, 0, 0], 
 [0, 0, 1, 1, 1, 0], 
 [0, 1, 0, 1, 0, 1], 
 [0, 0, 0, 0, 1, 0], 
 [0, 0, 1, 0, 0, 1], 
 [0, 0, 0, 0, 0, 0]]
6