- 프로그래밍 문제를 풀다보면 (특히 graph 관련 dfs, bfs 등을 활용한 탐색의 경우들) adjacent list 와 adjacent matrix 둘중 하나의 형태로 풀리는 경우가 많습니다.
- 저 같은 경우는 주로 시간제약 문제가 많은 관계로 adjacent list + bfs (or dfs) 로 문제를 많이 풉니다.
- 하지만 adjacent matrix 로 문제를 훨씬 더 빠르고 쉽게 경우도 있습니다. (가중치가 주어진 최단경로 등)
- 위와 같은 경우들을 위해 graph 를 표현하는 2가지 방법에 대해 정리합니다.
1. Adjacent list
- Graph 에서 node 사이들의 관계를 나타내는 방법입니다.
- python 에서의 구현 방법은 대락 2가지라고 생각할수 있습니다. 개인적으로 노드들의 데이터 형식(정수 혹은 문자)에 따라 2가지 방법(list, dictionary)로 구현합니다.
- node들이 int type 일 경우 list 를 사용 2차원 nested list 를 사용합니다.
- node들이 str type 일 경우 dictionary 를 사용하여 구현합니다.
- dictionary 가 int, str type 를 모두 키값으로 받을 수 있다는 점에서는 python에서 dictionary로 구현하는 것이 편하다고 생각합니다. - 장점 : adjacnet matrix에 비해 메모리를 적게 씁니다. 따라서 (https://www.acmicpc.net/problem/18352) 와 같이 메모리 제한이 있는 문제에 효과적입니다.
- 단점 : 노드들 관계를 확인하려면 해당 노드의 저장된 (linked) list 를 순회해야 됩니다. 따라서 시간 제한이 있는 문제에 적합하지 않을 수 있습니다.
형태
#1. list
# n은 노드의 개수
n = 4
# adj_lst의 row index를 출발하는 node로 지정하여 이에 해당하는 도착지점 node들을 list를 저장해 줍니다.
adj_lst = [[] for _ in range(n+1)]
adj_lst[1].extend([2,4])
adj_lst[2].extend([3])
adj_lst[3].extend([1])
adj_lst[4].extend([2,3])
# dictionary
# adj_lst_dict 의 key에는 출발 노드로 지정 이에 해당하는 도착지점 node들을 list로 만들어 value 값으로 지정해줍니다.
adj_lst_dict = {}
adj_lst_dict[1] = [2,4]
adj_lst_dict[2] = [3]
adj_lst_dict[3] = [1]
adj_lst_dict[4] = [2,3]
2. Adjacnet Matrix
- Graph 에서 node 사이들의 관계를 나타내는 방법입니다.
- python 에서는 nested list 를 사용하여 구현하는 방법이 일반적이라고 생각합니다.
- 장점1 : 가선의 가중치를 반영할 수 있습니다. 이러한 특성으로 인해 Dijkstra, Floyd-Warshall 과 같이 최단거리 알고리즘에 쓰입니다.
- 장점2 : Node들의 관계를 쉽게 알 수 있습니다. graph[node1][node2] 와 같이 O(1)로 확인 가능합니다. 즉 시간 제한이 있는 문제에 효과적입니다.
- 단점 : O(n^2)의 메모리를 사용합니다. 공간 제약에 있는 문제에 적합하지 않을 수 있습니다.
형태
# n : node 개수
# 편의상 node가 0부터 시작한다고 가정하겠습니다.
n = 4
graph = [[0]*(n) for _ in range(n)]
graph[0][1] = 1
graph[0][3] = 1
graph[1][2] = 1
graph[2][0] = 1
graph[3][1] = 1
graph[3][2] = 1
# 대각선은 1 로 채워줍니다.
graph[0][0] = 1
graph[1][1] = 1
graph[2][2] = 1
graph[3][3] = 1
for row in graph:
print(row)
# 출력 결과 (1 : 연결, 0 : 연결 X)
# [1, 1, 0, 1]
# [0, 1, 1, 0]
# [1, 0, 1, 0]
# [0, 1, 1, 1]
# 문제에 따라서 1 대신 간선의 가중치를 넣어줄 수도 있습니다.
댓글