[알고리즘] 그래프와 DFS, BFS

1. 그래프란?

그래프는 '노드 (Node) 와 각각의 노드를 연결하는 간선(Edge)'으로 구성된 자료구조이다. 쉽게 설명하면 각각의 객체들과 그것을 잇는 선들의 집합이라고 생각하면 된다. 실생활에서 우리가 대표적으로 보는 그래프 형태의 이미지는 지하철 노선도를 떠올릴 수 있다. 각각의 역과 역을 잇는 선들의 집합으로 그래프의 형태를 이루고 있다고 이해하면 알기 쉽다.

그래프는 또한 다음과 같은 다양한 특성을 지닌다.

• 노드(Node)는 다른 이름으로 정점(Vertex)라고도 불린다.
• 연결 방향에 따라서 양방향, 단방향, 무방향이 될 수 있다.
• 넓은 범위에서는 트리 역시 그래프의 일종이다.
• 인접 : 두 개의 노드가 간선으로 직접 연결되어 있는 상태를 말한다.
• 가중치 : 간선에 따라 할당된 값 또는 비용을 통해 간선의 특성을 나타낸 것을 의미한다.
• 시작위치는 어디든 상관없지만, 코드로 구현할 때는 처음부터 하는게 좋다.

이외에도 그래프의 특성에 따라 방향 그래프, 연결 그래프, 비순환 그래프 등등으로 분류하지만 우선은 최소한도로만 이해하고 그래프를 직접 구현해보면서 나중에 확인해보자.

---

2. 그래프의 구현

그래프를 구현하는 방식은 크게 2가지가 있다.

2-1 인접 행렬을 활용한 구현

한 노드가 다른 노드와 어떤 관계를 맺는지에 대해 N개의 노드를 가지는 그래프에 대해 N * N 배열로 표현하는 방식이다. 아래 코드를 기반으로 이해해보자.

n = 4 # 전체 노드의 갯수
graph = [[False] * n for _ in range(n)] # 그래프 초기 설정
graph[0][2] = True # 0번 노드에서 2번 노드로 가는 간선이 존재한다.
# [0,0,1,0]
# [0,0,0,0]
# [0,0,0,0]
# [0,0,0,0]

# 만약 간선의 가중치 있다면 False, True 대신 가중치를 적자.

위처럼 2개의 노드를 잇는 간선을 2차원 배열의 인덱스로 표시한 뒤, 실제 가는 간선이 있다면 위와 같이 표시하면 되고, 만약 방향성이 존재하는 단방향이라면 가는 간선 방향으로 1개만 True, 양방향 그래프라면 [1][2] , [2][1] 모두 True로 변경해주면 된다.

장점

• 조회 시간이 매우 빠르다.(O(1))
• 구현하기가 쉬움.

단점

• N * N의 형태로 만들기 때문에 입력 노드가 많으면 메모리 낭비가 커짐.
• 희소 그래프, 즉 노드 수에 비해 간선 수가 매우 적은 그래프는 메모리 낭비가 심함.

2-2 인접 리스트를 활용한 구현

인접 리스트는 한 노드에서 넘어갈 수 있는 다른 노드 정보를 배열로 나타내는 방식을 말한다. 인접 행렬에 비해 말이 조금 어려워보이는데, 코드를 먼저 이해하자.

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

# graph = [
#     [(1, 3)],
#     [(0, 3), (2, 1)],
#     [(1, 1), (3, 4)],
#     [(2, 4)],
# ]

# 1번 노드에서 3번 노드로 가는 비용이 7인 간선을 추가하려면?
# graph[1].append((3, 7))

쉽게 설명하면, 맨 밑의 주석처럼 각 노드 별로 갈 수 있는 노선과 그 가중치에 대한 정보를 쌍으로 각각 정리한다. 이렇게 하면 인접행렬과 반대되는 장단점을 가지게 된다.

장점

• 실제 연결된 노드에 대해서만 값을 담기 때문에 메모리 효율적임.
• 희소 그래프에 대해서도 속도가 빠름.

단점

• 특정 노드에 연결된 노드 개수가 많을 수록 탐색 시간이 오래걸림(O(N))
• 구현하기가 상대적으로 어려움.

하나의 방법만 사용하는 것이 아니라 상황에 따라 각 특성을 이해하고 구현하는 것이 좋다. 참고로 노드 개수가 1,000개 미만이라면 희소 그래프 같은 형상이 아닌 이상 인접행렬을 쓰는게 구현하는 입장에서 좋다.

	공간 복잡도	시간 복잡도	기타
인접 행렬	O(N^2))	O(1)	구현이 상대적으로 쉬움
인접 리스트	O(N^2))	O(N)

---

지금까지 그래프가 어떤 것이고, 그래프를 코드로 어떻게 구현하는지 알아봤다면 그래프를 탐색하는 대표적인 방법 2가지에 대해서 알아보자. 크게 BFS와 DFS가 있다.

3. DFS(깊이 우선 탐색)

DFS는 더 이상 탐색할 노드가 없을 때까지 우선 탐색하고, 그 뒤에 최근에 방문했던 노드로 돌아가 가지 않았던 노드를 방문하는 방식을 말한다. 쉽게 말해 그 노드와 연결된 리프 노드까지 다 훑어보고 더 이상 없으면 최근에 방문했던 직전 노드로 돌아가서 확인하는 방식이다. DFS는 주로 재귀와 스택을 이용해서 구현하는데 다음과 같은 과정을 따른다.

1. 스택이 비었는지 확인하고, 비었다면 모든 노드를 방문헀으므로 탐색을 종료한다.
2. 스택에서 노드를 팝한다. 팝한 노드는 최근에 스택에 푸시한 노드이다.
3. 팝한 노드의 방무 여부를 파악하고 방문하지 않았다면 방문 처리한다.
4. 방문한 노드와 인접한 모든 노드를 확인한다. 그리고 그 중에서 아직 방문하지 않은 노드를 스택에 푸시한다. 스택은 FILO 구조이기때문에 방문 순서를 오름차순으로 고려한다면 역순으로 푸시해야한다.
   (1과 인접한 노드가 4,5라면 스택에는 5를 먼저 넣고 그다음 4를 넣는다)

여기까지만 보면 이해하기가 쉽지 않은데 먼저 그림으로 다음과 같은 그래프가 있을 때 탐색하는 방식을 이해해보자.

이제 차례대로 그래프가 DFS 형태로 탐색하는 과정을 나열해보면

• 스택에는 처음 방문 예정인 노드를 우선 푸시한다. [1]
• 1에 방문한다. 1을 팝한 뒤에 방문한 적이 없다면 방문 처리를 한다. []
• 방문 처리를 한 뒤에 1과 인접하면서 방문하지 않은 노드를 5 -> 4 순서로 푸시한다(오름차순) [4, 5]
• 같은 방식으로 나중에 넣은 4를 팝한다. 4의 방문 여부를 확인하고 처리한다. [5]
• 4와 인접한 노드인 2,3을 3 -> 2 순서로 푸시한다. [2,3,5]
• 같은 방식으로 나중에 넣은 2를 팝한다. 2의 방문 여부를 확인하고 처리한다. [3,5]
• 2와 인접한 노드면서 방문처리를 하지 않은 3을 푸시한다.(방문 처리는 pop할때 하는 걸 잊지 말자) [5]
• 3을 팝하고 방문처리를 한다. 3과 인접한 노드는 없으므로 아무것도 푸시하지 않는다.[5]
• 5를 팝하고 방문처리를 한다. 스택이 비었으므로 탐색을 종료한다.

위와 같은 DFS의 일련의 과정을 코드로 나타내면 다음과 같이 2가지 방식으로 표현한다.

# 코드의 큰 형태
# def dfs(<현재 위치>, <방문 배열>):
# 	if <마지막에 도달하거나, 더 이상 진행할 수 없을 때>: return
#	<방문 배열에 현재 위치 방문 처리>
# 	<이번 방문에서 처리할 사항들>
#	dfs(<다음 위치>, <방문 배열>)


# 스택을 이용한 방식
def dfs(idx):
    stack = []
    stack.append(idx)
    while stack:
        current = stack.pop()
        print(f"{current} 방문!")
        visited[current] = True
        for adj in graph[current]:
            if not visited[adj]:
                stack.append(adj)
                visited[adj] = True

# 재귀함수를 이용한 방식
def dfs_recursive(idx):
    if visited[idx]: # 방문한 노드는 다시 방문할 필요 없음.
        return
    visited[idx] = True # 이 노드를 방문 처리
    print(f"{idx} 방문!")
    for i in graph[idx]: # 주변 노드들에 대해 하나씩 탐색을 시도
        dfs(i)

# 그래프 초기 설정
n = 5
graph = [[] for  _ in range(n + 1)]
graph[1].append(2)
graph[1].append(4)
graph[2].append(4)
graph[4].append(1)
graph[4].append(5)
graph[5].append(3)
visited = [False] * (n + 1)
dfs(1)
dfs_recursive(1)

두 가지 방식 모두 괜찮기 때문에 더 손에 익은 방식으로 문제를 풀거나 코드를 이해하면 될 것 같다.

---

4. BFS(너비 우선 탐색)

현재 위치에서 가장 가까운 노드부터 모두 방문한 뒤 다음 노드로 넘어간다. 그 뒤에 다시 가까운 노드부터 차례대로 방문하는 방식을 말한다. 모든 노드를 차례대로 살펴보기 때문에 여러 길 중에 최선의 길을 찾기 좋아 최단 경로 문제에서 자주 등장하는 방식이다. BFS는 주로 큐를 이용해서 구현하는데 다음과 같은 순서를 따른다.

1. 큐가 비었는지 확인한다. 큐가 비었다면 방문할 수 있는 모든 노드를 방문했다는 뜻으로 종료한다.
2. 큐에서 노드를 팝한다.
3. 팝한 노드와 인접한 모든 노드를 확인하고 그 중 아직 방문하지 않은 노드를 큐에 푸시하며 방문 처리한다.

다시 위에서 사용했던 그래프를 활용해 과정을 알아보자.

위와 같은 그래프일 때, 너비 우선 탐색의 탐색 과정을 차례대로 나열하면

• 시작 노드 1을 큐에 푸시하고 방문 처리한다.
• 1을 팝하고 인접한 노드 4,5를 순서대로 푸시하고 방문하지 않았으므로 방문처리한다.
• 4를 팝한 후, 4와 인접한 2,3을 확인한다. 아직 방문하지 않았으므로 2, 3을 순서대로 큐에 푸시하고 방문처리한다.
• 5를 팝한 후 인접한 1과 4를 본다. 이미 방문했으므로 아무것도 하지 않는다. 나머지 노드들도 마찬가지로 자신과 인접한 노드들을 모두 방문했으므로 차례대로 팝한다.
• 큐가 비게 되면 모든 탐색을 완료했다.

이렇게 차례대로 큐에 넣고 한 개씩 빼면서 확인하는 형태로 진행된다. 어떤 그래프를 나타낸 리스트를 줬을 때 BFS 하는 함수를 만든다고 하면 다음과 같다.

# 코드의 큰 형태
# queue = []
# queue.append(<시작 위치>)

# while queue:
#	<현재 값> = queue.pop()
# 	<방문 배열에 현재 위치 방문 처리>
#	<이번 방문에서 처리할 사항들>
#	if <다음 위치를 방문할 수 있을 때> : queue.push(<다음 값>)

def bfs(idx):
    from collections import deque
    queue = deque()
    queue.append(idx)
    visited[idx] = True
    while queue:
        idx = queue.popleft()
        print(f"{idx} 방문!")
        for i in graph[idx]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

---

DFS와 BFS의 차이점

	DFS(깊이 우선 탐색)	BFS(너비 우선 탐색)
구현	스택 또는 재귀함수로 구현	큐를 이용하여 구현
문제유형	경로의 특징을 기억해야하는 문제 - 경로에 같은 숫자가 있어선 안된다... 등	최단거리를 구해야 하는 문제
	백트래킹이나 그래프의 사이클을 감지해야되는 경우	네트워크 분석 문제

위 문장만 보면 BFS가 적을 것 같지만, 의외로 재귀 문제 때문에 BFS로 푸는게 훨씬 낫다. 가능하면 문제는 백트래킹 같은 경우가 아니라면 BFS로 풀자.