[방학의 PS] DFS와 BFS - BOJ_2606

어제 살짝 예고 드렸듯이 오늘은 DFS와 BFS의 구현에 대해 심층적으로 분석해보고자 합니다. 이 글은 자료구조와 알고리즘을 개략적으로나마 훑어보신 분들을 대상으로 한 글이기 때문에 DFS가 뭐고 BFS가 무엇인지에 대한 설명은 생략하도록 하겠습니다.

 

그럼 이제부터 본격적으로 다음과 같은 단계에 따라 DFS와 BFS를 구현해보도록 하겠습니다.

 

• 1단계 그래프 생성
• 2단계 DFS와 BFS의 공통점에 대해서 생각
• 3단계 DFS와 BFS를 각각 구현

1. 그래프 생성

 

당연하지만 그래프부터 생성해야 합니다. 당연하지만 그래프는 문제에서 주어지는 방식, 프로그램이 요구하는 방식에 따라 생성하는 방법이 천차만별이긴 합니다. 저는 아래와 같은 방식으로 구현했습니다만 사실 별로 중요한 코드는 아니라고 봅니다.

# n은 노드의 개수, m은 엣지의 개수

def graph_generate(n, m):
    graph = [[] for _ in range(n + 1)]

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

제가 의견을 나누고 싶은 것은 그래프를 과연 어떤 자료형으로 구현할 것인가하는 것입니다. 그래프를 구현하는 수많은 코드를 보면 어떤 분은 dictionary를 활용하셨고 어떤 분은 앞서 말씀드린 set 자료형을 활용하셨습니다. 그런데 저는 2차원 배열로 그래프를 생성하는 것이 가장 적절한 것 같다고 결론을 내렸습니다. 왜냐하면 2차원 배열의 경우 어느 프로그래밍 언어에나 공통적으로 존재하는 자료형이므로 범용성이 더욱 뛰어나다고 생각되었기 때문입니다. 반면 dictionary나 set의 경우 파이썬에만 있는 자료형으로 알고 있습니다.

 

 

2. DFS와 BFS의 공통점에 대한 고민

 

이제 그래프도 구현했으니 위 함수에서 return되는 graph를 활용하여 dfs 함수와 bfs 함수를 구현해봅시다. 당연히 두 함수가 최대한 유사한 형태를 이루고 있어야 readability가 높겠죠? 따라서 두 함수의 공통점을 먼저 생각해볼 것입니다.

 

• 1) 앞서 언급했듯이 2차원 리스트의 graph를 파라미터로 갖습니다.
• 2) 어디서 탐색을 시작할 것인지 주어져야 할 것이므로 시작 노드인 start를 파라미터로 갖습니다.
• 3) 한 번 방문했던 곳은 다시 방문하지 않습니다. 어떤 노드를 방문했는지 기억하기 위해 visited = [False] * (n + 1) 리스트를 파라미터로 갖습니다.
• 4) 경로를 방문할 때마다 방문한 노드를 print(node, end = ' ')로 출력하기로 해봅시다.

위와 같이 공통점에 대해 생각하며 파라미터와 무엇을 출력할 것인가를 결정했습니다. 함수를 구현하다보니 느끼는 것인데 함수 시그니처(파라미터, 반환 등)만 잘 정의해도 함수 구현의 반 이상은 끝났다는 느낌이 듭니다.

 

 

3.1 DFS의 구현

 

깊이 우선 탐색(Depth First Search)

 

이제 DFS를 구현해봅시다. DFS는 위에서 보다시피 계속해서 파고드는 탐색 방법입니다. 재귀로 구현하면 효과적일 것이란 감이 오시나요? 저는 감이 오지 않았습니다ㅎㅎ. 그래서 코드와 그래프를 계속 쳐다보며 경로를 따라가거나 분석해보니 어느 정도 느낌이 오더라고요.

 

사고 과정은 다음과 같습니다.

 

• 1) 시작 노드(start)를 방문합니다. 따라서 다시 방문하지 않기 위해 visited[start] = True를 선언합니다. 또한 start를 방문했다는 사실을 print(start, end = ' ') 로 출력합니다.
• 2) start노드와 연결된 첫 번째 노드(i)를 확인하여, 방문하지 않았다면, 즉 if not visited[i] 라면 1)을 똑같이 반복합니다.(재귀)

이제 이를 구현해 보면 다음과 같습니다.

def dfs(graph, start, visited):
    visited[start] = True
    print(start, end=' ')

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

    return

 

 

3.2 BFS의 구현

 

넓이 우선 탐색 (Breadth First Search)

 

BFS의 경우 queue를 통해 구현하게 됩니다. 위의 BFS 그림을 통해 설명드리면, 1을 방문하면 2, 3, 4를 queue에 저장합니다. 그리고 queue 내부의 요소들을 하나씩 방문하는데, 2를 방문하면 2와 연결된 5를 또 queue에 넣습니다. 그리고 queue의 다음 요소인 3을 방문하면 3과 연결된 6, 7을 다시 queue에 넣습니다. 이런 방식을 통하면 queue라는 자료구조에 BFS의 탐색 방법이 아주 적절하게 반영되는 모습을 볼 수 있습니다.

 

• 1) from collection import deque 와 queue = deque([])를 통해 queue를 구현하고, queue에 start노드를 push합니다.
• 2) 이제 queue 가 텅 빌 때까지 queue 내부의 요소를 방문하며, 또 queue 내부를 채웁니다. queue의 첫 번째 요소를 pop하고, 이를 방문합니다. 즉, queue의 첫 번째 요소가 새로운 start 노드가 됩니다.
• 3) start 노드를 방문하였으므로 이를 visited[start] = True를 통해 기억하고, print(start, end = ' ') 로 출력합니다.
• 4) 이제 start 노드에 딸린 노드(i)들을 queue에 push합니다. 이때 visited[i] = True 라는 코드가 삽입됩니다. 이 부분이 조금 까다로운 것 같습니다. 알고리즘 상으로는 어차피 방문하는 순서가 바뀌지는 않으므로 미리 방문 처리를 하는 것인데, 만약 여기서 방문 처리를 미리 하지 않으면 queue에 넣는 과정에서 중복으로 push되는 노드가 있기 때문입니다. 즉, 방문은 한 번에 한 곳씩 이루어지는데 queue에 push되는 node는 여러 개이므로 이 과정에서 어떤 노드가 중복 push 되는 것을 막기 위해 미리 방문 처리를 하는 것이라 생각하면 될 것입니다.

이제 이를 구현해보면 다음과 같습니다.

def bfs(graph, start, visited):
    queue = deque([start])
    
    while queue:
        start = queue.popleft()
        visited[start] = True
        print(start, end = ' ')
        for i in graph[start]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
    
    return

 

열심히 적어 봤는데 잘 이해가 되실지 모르겠네요. 어차피 단순히 제가 정리하려고 쓰는 것이긴 합니다만 말입니다ㅎㅎ;;

 

---

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

2606번: 바이러스

DFS로 구현할 것인가 BFS로 구현할 것인가는 자유이지만, 저 같은 경우 BFS로 구현해 보았습니다.

from collections import deque

def graph_generate(n, m):
    graph = [[] for _ in range(n + 1)]

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

def bfs(graph, v, visited):
    queue = deque([v])

    while queue:
        v = queue.popleft()
        visited[v] = True

        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
    
    return visited

n = int(input())
m = int(input())
graph = graph_generate(n, m)

visited = [False] * (n + 1)
ans = bfs(graph, 1, visited)
print(ans.count(True) - 1)