파이썬 알고리즘-53 (DFS/BFS) 경로탐색

53.경로 탐색(그래프 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줄에 걸쳐 연
결정보가 주어진다.

▣ 출력설명
총 가지수를 출력한다.

▣ 입력예제 1
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

▣ 출력예제 1
6

내 코드

def dfs(v):
    global cnt
    if v==n:
        cnt+=1
    else:
        visited[v]=True
        for i in range(n+1):
            if lst[v][i]==0:
                continue
            else:
                if visited[i]:
                    continue
                else:                   
                    dfs(i)
                    visited[v]=False
    
n,m=map(int, input().split())
lst=[[0]*(n+1) for _ in range(n+1)]
cnt=0
for _ in range(m):
    a,b=map(int,input().split())
    lst[a][b]=1
visited=[False]*(n+1)
dfs(1)
print(cnt)

인접행렬을 만들어, 반복문 안에서 경로가 있는(값이 1인) 노드로만 함수를 재귀적으로 실행하게 만든다. 그런데 이미 방문한 노드는 다시 방문할 수 없다. 이 부분에서 막혀서 힌트를 봐야했고, 그럼에도 불구하고 틀렸다. 그리고 가장 바깥쪽 함수가 다 실행된 후 방문한 노드에 체크를 해제해야 하는 것도 인식하지 못했다.

풀이

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)

반성점

• 경로 탐색도 이미 배운 내용이지만 전혀 기억하지 못했다.

배운 것

• 경로 탐색에서는 방문한 노드는 다시 방문할 수 없기 때문에 이를 확인할 수 있는 도구가 필요하며, 함수 실행이 한 번 종료되면 뒤로 돌아가야 하기 때문에 방문 체크를 해제해야 한다.