[Algorithm] DFS 이론 + 구현

❗DFS

깊이 우선 탐색이라는 그래프 탐색 기법으로 시작 노드에서 가장 깊숙히 들어가서 노드를 탐색한 후 다시 상위 노드로 이동하여 다른 루트를 탐색하는 방식이다.

DFS를 구현하는 방식으론 스택과 재귀 호출이 있는데 해당 포스트에선 재귀 호출로 설명하고자 한다!

 

❗동작 방식

위와 같은 그래프가 있고, 1번 노드에서 시작하여 탐색하고자 한다.

손으로 DFS를 풀 때는 1 -> 3 -> 6까지 탐색 후 더이상 나아갈 노드가 없기 때문에 3번 노드까지 거슬러 올라오게 된다.

그 후 3번의 자식 노드 중 방문하지 않은 4를 방문하고 이어서 탐색하면

결국 DFS의 방문 노드 순서는 1 -> 3 -> 6 -> 4 -> 2 -> 5이 된다.

 

❗파이썬 구현

위의 케이스를 파이썬 코드로 구현한 것이다.

graph = [[],[3,2],[3,1,4,5],[6,4,2,1],[3,2],[2],[3]]
visited = [0] * (7)

dfs(graph, 1, visited)

 

먼저, graph를 선언 시 2차원 배열로 선언하게 되고, 각 요소의 인덱스가 그래프의 노드 번호가 된다.

해당 인덱스에 있는 배열은 각각의 노드와 연결되어 있는 다른 노드의 집합이다!

그 다음 visited를 선언하여 노드를 거슬러 올 때, 방문 여부를 판단할 수 있도록 한다.

dfs 함수의 파라미터로 그래프, 방문 노드 번호, 방문 배열을 넣어준다.

 

def dfs(graph, v, visited):
    visited[v] = 1
    print(v, end=" ")

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

함수 구현부를 보면 v로 방문한 노드 번호를 받았기 때문에 visited 배열에서 방문 처리를 해준다.

graph[v]는 방문한 노드에 연결된 노드의 집합이고, 이를 i 변수로 하나씩 꺼내오게 된다.

i를 방문했는지 판단하고, 방문하지 않았을 경우만 i를 방문 노드 번호로 지정하여 dfs함수를 다시 호출한다.

 

아래는 코드 전문입니다.

def dfs(graph, v, visited):
    visited[v] = 1
    print(v, end=" ")

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

graph = [[],[3,2],[3,1,4,5],[6,4,2,1],[3,2],[2],[3]]
visited = [0] * (7)

dfs(graph, 1, visited)

 

❗참고 문제

https://www.acmicpc.net/problem/1260

https://radiant515.tistory.com/493

[Baekjoon] 백준 1260 DFS와 BFS Python