코딩테스트를 위한 기본 개념 1탄 - 그래프(Graph)

코딩테스트를 공부하며 그냥 문제만 풀기도 하고 개념을 보고 공부하기도 했는데, 뭔가 따로노는 느낌이 들었다.

문제만 풀다보면 막혀서 답지 보고 그 때는 이해한 것 같아 넘어갔다가 나중에 까먹을 때가 많았고,

개념을 공부했을 때는 그래서 어떻게 구현하는건데? 하면서 결국 문제를 풀지 않으면 개념을 익히기 어려웠다.

 

그래서 적어보는 나를 위한 코딩테스트 개념 & 기본코드 간단 정리집. 

기본적인 개념을 익혀보고, 기본적인 코드를 익히고, 관련 문제를 정리해본다. 

 

 

목차

 

1. 그래프 (Graph) 개념

그래프는 실제 세계의 현상이나 사물을 정점(Vertext, 또는 노드(Node))과 간선(Edge)로 표현하기 위해 사용된다.

 

1.1 관련 용어

- 노드 (Node) : 위치를 의미. 정점(Vertex)라고도 함

- 간선 (Edge) : 위치 간 관계를 표시한 선으로 노드를 연결한 선 (Link, Branch라고도 함)

- 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 정점(노드)

- 정점의 차수 (Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수

- 진입 차수 (In-Degree) : 방향 그래프에서 외부에서 오는 간선의 수

- 진출 차수 (Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수

- 경로 길이 (Path Length) : 경로를 구성하기 위해 사용된 간선의 수

- 단순 경로 (Simple Path) : 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로

- 사이클 (Cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

 

1.2 그래프 종류

그래프는 방향 유무에 따라 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 나눌 수 있다.

 

1) 무방향 그래프

무방향 그래프 예시

• 방향이 없는 그래프. 간선을 통해 노드는 양방향으로 갈 수 있음
• 보통 노드가 A, B가 연결되어 있는 경우 (A, B) 또는 (B, A)로 표기함

 

 

2) 방향 그래프

방향 그래프 예시

• 간선에 방향이 있는 그래프
• 보통 노드 A, B가 A→B로 가는 간선으로 연결된 경우 <A,B> 로 표기함 (<B, A>와는 다른 의미)

 

 

2. 파이썬으로 그래프 구현하기

그래프는 인접 리스트와 인접 행렬 두 가지 방식으로 표현 가능한데, 파이썬에서는 딕셔너리와 리스트 자료구조를 사용해서 구현할 수 있다. 각 방법으로 아래의 그래프를 리스트로 구현해보자.

 

2.1 인접 행렬

graph = [[0, 1, 1, 1],
	 [1, 0, 0, 1],
         [1, 0, 0, 1],
         [1, 1, 1, 0]]

• 각 행과 열은 노드를 의미하는데, 연결되어 있으면 1, 아니면 0을 입력함. 노드 0은 노드 1, 2, 3 과 연결되어 있기 때문에 graph[0] = [0, 1, 1, 1] 이 되고, 노드 2는 노드 0과 3과 연결되어 있기 때문에 graph[2] = [1, 0, 0, 1]이 됨. 
• 무방향 그래프일 경우 대각선 대칭 그래프가 되지만 방향 그래프의 경우 대각선 대칭이 안됨
• 간선 별 가중치를 설정하는 가중치 그래프의 경우 1이 아닌 다른 값을 넣어 가중치를 표현함
• 방향 그래프의 경우 진출하는 노드에만 1을 표시함 (0 → 1 (반대는 X)인 경우 graph[0][1] =1, graph[1][0] = 0)

2.2 인접 리스트

graph = [
	[1, 2, 3],
	[0, 3],
	[0, 3],
	[0, 1, 2]
]

graph = {
    'A' : ['B', 'D'],
    'B' = ['A', 'C'],
    'C' = ['B', 'D'],
    'D' = ['A', 'C']
}

• 각각의 인덱스에 해당하는 노드에 연결된 노드들을 리스트 형태로 저장하는 방식. 노드 0은 노드 1, 2, 3과 연결되어 있기 때문에 graph[0] = [1, 2, 3]이 되고 노드 2는 노드 0, 3이 연결되어 있기 때문에 graph[2] = [0, 3]이 됨
• 노드를 문자열로 나열할 때는 딕셔너리 형태로 구현할 수 있어 편리함
• 가중치 그래프를 표현하기 위해선 연결 정보에 튜플이나 다른 방식으로 가중치를 추가적으로 입력해줘야 함
• 방향 그래프의 경우 진출하는 노드만 리스트에 담음 ( 0 → 1 (반대는 X)인 경우 graph[0] = [1], graph[1] = [])

 

2.3 인접 행렬 - 인접 리스트 비교

그래프 관련 코딩 테스트 문제를 풀다 보면, 모든 노드 간 연결 정보를 찾는 경우와 특정 노드 간 연결 정보를 찾는 경우가 있다. 각 상황 별로 비교해보면,

 

1) 모든 연결 정보를 찾아야 하는 경우 (인접 리스트 사용)

• 인접 행렬 : 각 행에 연결된 노드가 무엇인지 찾기 위해서 모든 노드가 연결되어 있는지 직접 확인해야 하기 때문에 시간 복잡도가 높음(O(|N|), N : 노드 수)
• 인접 리스트 : 해당 노드에 입력된 리스트 전체를 가져오면 되기 때문에 시간 복잡도가 낮음

2) 특정 노드 간 연결 정보를 찾아야 하는 경우 (인접 행렬 사용)

• 인접행렬은 graph[i][j]를 통해 노드 i와 노드 j가 연결되어 있는지를 바로 확인할 수 있음 (시간복잡도 : O(1))
• 인접리스트는 graph[i]에서 j가 있는지 탐색해야 하기 때문에 인접행렬보다 시간이 오래 걸림

 

3. 문제 풀어보기

실제 문제에서 그래프를 어떻게 구현하는지 적용해보자. 예시 문제는 백준 1260번: DFS와 BFS이다.

문제는 DFS와 BFS를 구현하는 것인데, 이번 글에서는 입력으로 들어오는 그래프를 구현하는 방법만 적어본다.

 

- 입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

* 입력 예제

백준 1260번 입력 예제

입력 예제를 살펴 보면, 노드는 4개, 간선은 5개이고 1번과 2번 노드, 1번과 3번 노드 등이 연결되어 있는 것을 확인할 수 있다. 이를 인접 행렬과 인접 리스트로 각각 구현해보자.

 

- 구현

1) 인접 행렬

n, m = map(int, input().split())
graph = [[0]*(n+1) for _ in range (n+1)]

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

 

n+1을 한 이유는 입력에서 n이 1이상의 값이니 노드 0이 없지만 파이썬 index는 0부터 시작하기 때문에 헷갈리지 않게 노드 0을 임의로 추가해준 것이다. 입력 조건 상 노드 0인 graph[0]의 리스트 내 모든 값은 0이 유지될 것이다.

 

입력 예제의 경우, 1 2가 들어왔을 때 노드 1인 graph[1][2]도 1이 표시되어야 하고, 노드 2인 graph[2][1]도 1이 표시되어야 하기 때문에 위와 같이 구현한다. 

 

2) 인접 리스트

n, m = 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)

 

인접 리스트의 경우 연결된 노드를 해당 노드의 인덱스에 추가해주면 되기 때문에 각 노드 별 리스트를 만든 후 해당 리스트에 연결된 노드의 값을 추가해주는 방식으로 구현할 수 있다.