[Algorithm] - DFS를 통한 모든 경우의 수

DFS

---

특정 Start를 기반으로 Node를 재귀로 타고 들어가 자신이 도착하는 경우의 수를 추출한다.

 

모든 경우의 수 구하기

• 아래 경우에서 Node 1에서 4로 가는 경우의 수를 탐색한다고 하여보자.
• DFS로 구현을 하게 된다면 일반적으로 1-2-3-4 탐색 후 끝나는 것이 일반적이지만, 우리는 모든 경우의 수를 구현해야 한다.

 

알고리즘

---

• 기존의 DFS코드를 활용한다.
• 이 때 나머지 경우에도 탐색을 해야하기 때문에 Visited edge값을 되돌려주고 임의의 값을 빼준다.

 

코드

---

n = 5
edges = [[1,2],[1,3],[2,3],[2,5],[3,4],[3,5],[5,4]]
from collections import defaultdict

def solution(n,edges):
    graphs = defaultdict(list)
    target = 4
    visited = [0]*(n+1)
    visited[1] = 1
    answer = []
    temp = []
    for start,end in edges:
        graphs[start].append(end)
        graphs[end].append(start)

    def dfs(node):    
        temp.append(node)
        if node == target :
            answer.append(temp[:])
            return
        for edge in graphs[node]:
            if not visited[edge]:
                #print( node , edge)
                visited[edge]=1
                dfs(edge)
                #print( 'edge :' , edge)
                visited[edge]=0
                temp.pop()

    dfs(1)
    print(answer)

solution(n,edges)