바이러스

백준 2606

방법1. DFS

---

n = int(input())
m = int(input())

graph = [[] for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b)
    graph[b-1].append(a)

visited = []
def dfs(graph, node ,visited):
    visited.append(node)
    for ad_node in graph[node-1]:
        if ad_node not in visited:
            dfs(graph, ad_node ,visited)
    return len(visited)-1

print(dfs(graph, 1, visited))

DFS를 이용하여 구현해보았다. 우선 입력받은 값을 DFS를 하기 편하도록 그래프를 만들어주었는데, 연관이 있는 수들은 서로의 리스트에 추가해줘야한다.
방문한 노드를 기록하기 위해 visited 리스트도 만들어주었다.
현재노드는 방문처리해주고, 현재노드가 가진 리스트 안의 인접노드들 중 만약 방문하지 않았다면 dfs를 해주면된다.
이처럼 dfs는 재귀함수로 구현이 가능하다.
또한 dfs는 스택으로도 구현이 가능한데, 인접한 노드들을 모두 탐색하고 넘어가는 것이 아닌 한 줄기를 끝까지 따라갔다가 끝의 인접노드들을 탐색하고 돌아오면서 처리하기 때문이다.

방법2. BFS

---

from collections import deque

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

queue = deque()
def bfs(graph, v, visited):
    queue.append(v)
    visited.append(v)
    while queue:
        node = queue.popleft()
        for ad in graph[node]:
            if ad not in visited:
                queue.append(ad)
                visited.append(ad)
    return len(visited)-1

visited = []
print(bfs(graph, 1, visited))

BFS는 큐(덱)를 이용하여 구현한다.
노드를 큐에 넣어주고 방문처리한다. 그리고 큐가 비어있지 않을 동안 큐에 넣은 노드를 꺼내 그 노드의 인접노드들에 대해서 또 큐에 넣어주고 방문처리하는 것을 반복한다. 그러면 큐의 특성에 따라 특정 노드의 인접노드 즉 이웃노드부터 탐색이 가능하다.

DFS

깊게 탐색하기. 재귀와 스택으로 구현이 가능하다. 인접한 노드 중 방문하지 않은 모든 노드를 저장해두고 가장 마지막에 넣은 노드만 꺼내서 탐색한다.

BFS

인접한 노드부터 탐색하기. 큐를 이용해 구현이 가능하다. 인접한 노드 중 방문하지 않은 모든 노드를 저장하고 가장 처음에 넣은 노드부터 탐색한다.


일반적으로 DFS보다 BFS가 좀 더 빠르다. DFS는 재귀함수로 간단히 구현하는 편이다.