그래프 이론 - 0. 소개

알고리즘을 공부하면서 처음 만나는 큰 고비는 어디일까? 난이도에 대한 체감은 사람마다 다르겠지만 대체로 그래프 문제에서 벽을 느끼는 경우가 많다. 내 경험에 비추어봐도 그러했고, 현재 속해있는 알고리즘 스터디의 스터디원들도 그러했고, 현업의 알고리즘 강사님 또한 교육생들이 가장 어려움을 겪는 파트로 그래프를 꼽으셨다.

 

solved.ac의 태그에 따르면 그래프 이론은 백준에서 분류된 문제 유형 중 5번째로 많다. 흔히 출제되지 않는 문제라면 그냥 배제해버릴 수도 있었겠지만, 그래프 문제는 자주 등장하는 유형의 문제이기 때문에 절대로 포기해서는 안 된다.

 

그렇다면 사람들이 그래프 문제를 처음 접했을 때 어려움을 겪는 이유는 무엇일까? 아마도 평소 코드를 작성할 때 문자열, 배열, 사칙연산 등은 자주 사용되는데 반해 그래프 구조를 접할 일이 없기 때문일 것 이다. 다른 이유로는 자주 접하는 문자열 및 배열이 선형 구조인데 반해 그래프는 비선형 구조라 더 생소하게 느껴지는 것 때문일 것 같다. 이 글에서는 어렵게 느껴지는 그래프 문제를 어떻게 접근해야 하는지에 대해 다루고자 한다.

 

 

그래프(Graph)의 정의

일반적으로 그래프는 정점(vertex)과 정점들을 연결하는 간선(edge)로 구성된 자료구조를 의미한다.

 

조금 더 세분화 해보면, 간선의 방향 존재 유무에 따라 무향 그래프(undirected graph)와 유향 그래프(directed graph)로 분류할 수 있고, 간선에 가중치가 존재 하는 그래프(weighted graph)와 가중치가 존재하지 않는 그래프(unweighted graph)로 나눌 수 있다.

 

 

그래프의 표현

그래프를 처음 접했을 때의 최대 난관은, 주어진 그래프 구조를 어떻게 코드로 표현할 것 인가 이다. 위에서 언급했듯이, 그래프는 정점과 정점을 연결하는 간선으로 이루어진 자료구조 이다. 따라서 초점을 맞춰야 할 곳은 어떤 정점들 끼리 연결되어 있는지가 될 것이다. 그래프에 존재하는 모든 정점들에 대하여, 각각의 정점들이 연결되어 있는 정점을 담은 배열을 만드는 걸 시도해볼 수 있다.

 

위의 그림과 같은 그래프가 주어졌다고 가정하자. (편의상 간선에 방향 및 가중치는 존재하지 않는다고 가정)

각 정점들과 연결되어 있는 정점을 나타내는 테이블을 만들어 보면 다음과 같을 것 이다. 

 

정점	연결된 정점
1	2,5
2	1,3,5
3	2,4
4	3,5,6
5	1,2,4
6	4

 

 

위 표를 코드로 표현한다면 아래와 같을 것 이다. (아래와 같은 형태의 배열을 인접 리스트(adjacency list) 라고 부른다.)

# list를 이용한 표현 (DAT: Direct Access Table)
graph = [[], [2,5],[1,3,5],[2,4],[3,5,6],[1,2,4],[4]]

# dictionary를 이용한 표현
graph = {1:[2,5],2:[1,3,5],3:[2,4],4:[3,5,6],5:[1,2,4],6:[4]}

 

 

먼저 이차원 배열을 이용한 표현을 살펴보면, 배열의 가장 앞에 빈 리스트를 추가하였다. 그 이유는 정점의 이름을 이용하여 호출하기 위해서인데, 파이썬의 배열은 0번 인덱스부터 시작하고 현재 주어진 정점은 1부터 시작하므로 배열의 가장 앞에 빈 리스트를 추가함을 통해서 1번 정점이 1번 인덱스를 부여받게 하였다. 이를 통해 i번 정점과 연결된 정점은 graph[i]로 조회할 수 있다.

dictionary는 정점의 이름이 정수형이 아닌 문자형 등으로 주어지는 문제, 혹은 주어진 정점이 연속된 정수가 아니면서 정점의 범위가 매우 큰 경우 사용을 고려해볼 수 있다. 

 

그 다음은 실제 문제에서 그래프의 정보가 입력으로 주어질 때 인접 리스트를 생성하는 코드를 작성할 차례다.

문제마다 주어지는 입력형태가 조금씩 다르긴 한데, 백준에서 많이 사용되는 입력 방식은 아래와 같다.

6 7 # 1번째 줄: 정점 및 간선의 갯수
1 2 # 2번째 줄~: 간선의 정보 (시작 정점, 끝 정점)
1 5
2 3
2 5
3 4
4 5
4 6

 

 

아래의 코드를 통해 인접 리스트를 만들어볼 수 있다.

# vertex: 정점의 갯수, edges: 간선의 갯수
vertex, edges = map(int, input().split()) 

# 인접 리스트 - 배열 안에 정점의 갯수+1 만큼 빈 배열을 생성
graph = [[] for _ in range(vertex+1)] 

# 간선의 정보를 입력받아 인접 리스트에 포함
for _ in range(edges):
    start, end = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start) # 간선이 양방향일 경우에만

 

 

그렇다면 간선에 가중치가 있다면 어떻게 해야 할까? 복잡하게 생각 할 필요 없이, 인접 리스트를 작성할 때 인접한 정점만 포함시키는 것이 아니라 (가중치, 인접 정점) 의 형태로 가중치를 같이 포함시키면 된다. 

 

인접 리스트 말고도 인접 행렬(adjacency matrix) 라는 구조를 통해서도 표현이 가능한데, 메모리를 많이 사용하기 때문에 정점의 개수가 많다면 사용하기 힘든 방식이라 따로 소개하지 않았다.