그래프

그래프는 트리와 달리 네트워크 모델이다. 노드가 N개인 트리에서 간선은 항상 N-1개 이지만 그래프에서는 간선의 갯수와 노드의 갯수에는 정해진 규칙이 없다.

깊이 우선 탐색

그래프에서 노드를 순회할 때 쓰는 알고리즘은 대표적으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있다. 이번에는 깊이 우선 탐색에 대해서 알아보고 이를 실전 알고리즘 문제에 적용시켜 이해한다.

방식

그래프에서는 시작 노드를 어떻게 정하느냐에 따라 탐색 순서가 달라진다. 깊이 우선 탐색에서는 아래와 같은 순서를 가질 수 있다.

1. 시작할 노드를 스택에 담고 방문 처리 한다.
2. 스택에서 노드를 꺼내어 인접한 노드들 중 방문하지 않은 노드들을 스택에 넣고 방문 처리한다.
3. 방문하지 않은 노드가 없을 때까지 위 과정을 반복한다.

일반적으로 시작 노드가 1번이고 인접한 노드들이 2번과 3번 노드가 있을 경우 숫자가 낮은 노드부터 먼저 탐색한다.

구현

파이썬에서 그래프는 2차원 배열로 표현할 수 있다. 각 인덱스는 i번 노드를 가르킨다. i번 노드는 n개의 인접 노드들을 가질 수 있다. 예를 들어 아래와 같이 표현할 수 있다.

graph = [
  [],
  [2, 3], # 1
  [1, 4], # 2
  [1], # 3
  [2] # 4
]

1번 노드는 2번 3번 노드와 인접해있다. 2번 노드는 1번과 4번 노드와 간선으로 연결되어 있다. 위와 같이 파이썬에서 그래프를 표현할 수 있다.

백준 2606번 바이러스

바이러스 문제 원문

해당 문제에서는 시작 노드는 항상 1번이다. 이 문제는 깊이 우선 탐색으로 풀어도 되고 너비 우선 탐색으로 풀어도 된다. 여기에서는 위에서 정리한 깊이 우선 탐색을 사용해서 문제를 해결한다.

입력에서 첫째 줄은 컴퓨터의 수라고 되어있는데 이는 노드 갯수를 의미하고 둘째 줄은 간선을 의미한다. 입력받은 값들을 기반으로 2차원 배열을 이용해서 그래프를 표현한다. 해당 문제는 2차원 배열로 구성하면 아래와 같이 구성할 수 있다.

import sys
input = sys.stdin.readline

C = int(input().rstrip())
S = int(input().rstrip())
graph = [[] for _ in range(C + 1)]

for i in range(S):
  node, node2 = map(int, input().split())
  graph[node].append(node2)
  graph[node2].append(node)

2차원 배열로 그래프를 구성하고 dfs 함수를 구현한다.

def dfs():
  visited = []
  stack = [graph[1]]
  cnt = 0

  while stack:
    cur = stack.pop()
    for i in cur:
      if not i in visited:
        visited.append(i)
        stack.append(graph[i])
        cnt += 1

  print(cnt - 1)

스택에 시작 노드를 넣는다. 여기에서는 항상 시작 노드가 1번 노드이기 때문에 1번을 넣고 시작한다. 스택에서 하나를 꺼내어 인접 노드들을 방문 처리하고 스택에 모두 넣고 스택이 빌 때까지 반복한다. cnt 변수에 탐색한 노드들의 갯수가 저장되는데, 여기에서는 1번 노드를 제외하니 cnt - 1개가 정답이 된다.