그래프 (Graph)
그래프의 정의
그래프(G)는 정점(vertex)들의 집합 $V$와 이들을 연결하는 간선(edge)들의 집합 $E$로 구성된 자료구조입니다.
위와 같은 그래프가 있다고 할 때, 정점은 A, B, C, D, E, F 입니다.
또 정점들을 연결하는 간선들은 A-B, B-C, B-E, C-D, E-D, E-F, E-D 입니다.
즉, 위의 그래프는 정점들의 집합 $V = \lbrace A,B,C,D,E,F \rbrace$와 이들을 연결하는 간선들의 집합 $E=\lbrace (A,B),(B,C),(B,E),(C,D), (E,D), (E,F) ,(E,D) \rbrace$로 이루어져 있습니다.
그래프의 활용
그래프는 이렇듯 연결 관계를 표현하기에 현실 세계의 사물이나 추상적인 개념들을 잘 표현할 수 있습니다.
- 도시들을 연결하는 도로망: 도시(vertex), 도로망(edge)
- 지하철 연결 노선도: 정거장(vertex), 정거장을 연결한 선(edge)
- 컴퓨터 네트워크: 각 컴퓨터와 라우터(vertex), 라우터 간의 연결 관계(edge)
- 소셜 네트워크 분석: 페이스북의 계정(vertex), follow 관계(edge)
그래프의 종류
위와 같은 기본적인 그래프에서 시작하여, 다양한 그래프를 살펴볼 수 있습니다.
1. 무향 그래프(undirected graph) vs 방향 그래프(directed graph)
앞서서 다룬 그래프를 다시 살펴보도록 합시다.
위와 같은 그래프는 A→B로 갈 수 있으며, B→A로도 갈 수 있기에 무향 그래프(**undirected graph)**라고 합니다. 따로 방향이 안 정해져 있기 때문입니다.⁽¹⁾
한편 다음과 같이 간선의 방향이 정해져 있는 그래프도 있습니다.
위와 같이 방향이 정해져 있는 그래프를 방향 그래프(directed graph)라 합니다.
그래프를 잘 살펴보면 들어오는 간선과 나가는 간선으로 구분할 수 있습니다. 이때 들어오는 간선을 indegree라 하며, 나가는 간선을 outdegree라 합니다. 정점 B를 살펴보면 A와 C로부터 들어오는 indegree 2개, E로 나가는 outdegree 1개가 있는 것을 알 수 있습니다.
2. 단순 그래프 vs 다중 그래프
다시 그래프를 보도록 하겠습니다.
인접해 있는 두 정점과의 관계를 살펴보도록 합시다. $(A,B),(B,C),(B,E), (E,D) \cdots$ 등이 있을 것입니다. 이때 두 정점 사이에 indegree가 1개, outdegree가 1개인 그래프를 단순 그래프(simple graph) 라고 합니다.⁽²⁾
하지만 다음과 같이 여러 길이 존재 할 수 도 있습니다.
A에서 B까지 가는 방법이 총 3개 있습니다. 다시 말해, 인접해 있는 두 정점 A,B 사이에 A를 기준으로 ingree가 3개 outdegree가 3개가 있습니다.
이렇게 인접해 있는 두 정점 A,B의 관계에서 outdegree와 indegree가 2개 이상인 그래프를 다중그래프(Multigraph) 라고 합니다.
3. 가중치 그래프
다시 그래프를 보도록 하겠습니다.
현재 이 그래프에서는 A에서 B로 , B에서 E로 등 모든 경로의 비용(시간)이 동일하다고 가정했습니다. 하지만, 아래와 같이 경로마다 비용을 다르게 설정할 수 있습니다. 각 경로 마다 가중치가 다르다 하여 아래와 같은 그래프를 가중치 그래프(Weighted Graph) 라고 정의합니다.⁽³⁾
그래프의 구현
여러 가지 그래프를 보았으니, 이제 그래프를 구현하도록 하는 시간을 갖겠습니다. 그래프를 구현하는 방법으로는 총 3가지가 있습니다.
- 인접 행렬
- 인접 리스트
- 암시적 그래프
각 그래프를 구현 하는 방법을 알아보도록 하겠습니다.
1. 인접 행렬
행렬은 행(row)과 열(column)에 따라, 정보들을 직사각형 모양으로 배열한 것입니다.
다음 그래프가 있을 때, 각 정점들을 하나의 행(가로)과 열(세로)이라 생각할 수 있습니다.
와 같이 말이죠. 그 후 그래프의 연결 관계를 생각해 볼 수 있습니다. 정점끼리 연결되어 있으면 1 ,연결되어 있지 않으면 0을 대입해 보도록 합시다.
흔히 행렬을 만들기 위해서는 이중리스트를 사용합니다.
위와 같은 matrix가 있을 때 코드로 표현하면 다음과 같습니다.
matrix = [[1, 2, 3], [4, 5, 6]]
인접행렬 역시 마찬가지입니다. 다만, 리스트에서 A,B ... index는 존재 하지 않기에 A를 0, B를 1과 같이 생각해 줍니다.
matrix = [
[0, 1, 0, 0, 0, 0],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 0, 0],
[0, 0, 1, 0, 1, 1],
[0, 1, 0, 1, 0, 1],
[0, 0, 0, 1, 1, 0],
]
위 그래프에서 특징적인 점은 자기 자신(ex A-A, B-B)을 연결하는 간선이 없기 때문에, 대각선의 값이 모두 0이라는 점과 무향 그래프이기 때문에 대각선을 기준으로 대칭입니다.
이제 저희는 모든 그래프에 대해서 인접 행렬을 그릴 수 있습니다. 하지만 인접 행렬이 만사는 아닙니다. 다음과 같이 정점은 엄청 많은데, 간선의 개수가 적을 때는 비효율적입니다.
다음과 같이 A-B의 관계를 제외하고는 모두 0으로 나타내기 때문에, 메모리 사용 측면에서 비효율적이라고 할 수 있습니다. 그래프는 연결 관계를 나타내는 것이 중요한데, 0은 정보로서 가치가 떨어집니다.
인접 리스트를 사용하면, 위와 같은 문제를 해결할 수 있습니다.
2. 인접 리스트
인접 리스트는 딕셔너리 {}의 형태로 정의됩니다. 딕셔너리는 key와 value로 정의되는 자료구조입니다. 인접 리스트 같은 경우, key에는 정점들이 들어가며, value에는 list 형태로 연결 관계를 표시해 줍니다.
실제 예시를 봐보도록 합시다.
graph = {
"A": ["B"],
"B": ["A", "C", "E"],
"C": ["B", "D"],
"D": ["C", "E", "F"],
"E": ["B", "D", "F"],
"F": ["D", "E"],
}
위에서 인접 리스트 같은 경우, 정점들이 많고, 간선이 적은 경우 대부분의 정보가 0으로 채워지기 때문에 비효율적이라고 하였습니다.
하지만 인접 리스트를 사용하게 되면, 이를 간편하게 표현할 수 있습니다.⁽⁴⁾
graph = {
"A": ["B"],
"B": ["A"],
"C": [],
"D": [],
"E": [],
"F": [],
}
3. 암시적 그래프
코딩 테스트에서 제일 많이 활용되는 암시적 그래프를 다루어 보도록 하겠습니다. 그래프 문제를 풀다 보면 다음과 같은 문제들을 자주 접해 볼 수 있습니다.
다음과 같이 흰색이 길이고, 검은색이 벽인 미로가 있다고 합시다. 전혀 그래프 같지 않지만, 암시적으로 그래프처럼 표현할 수 있습니다.
벽에는 1의 값을, 길에는 0의 값을 넣음으로써, 구분해 보도록 합시다. 그리고 각 영역을 좌표의 개념을 도입하여 표현할 수 있습니다.
graph = [
[1, 1, 1, 1, 1],
[0, 0, 0, 1, 1],
[1, 1, 0, 1, 1],
[1, 0, 0, 0, 0],
[1, 1, 1, 1, 1],
]
위의 표현 방식 같은 경우, 연결 관계를 직접적으로 나타내지는 않았습니다.
하지만 상하좌우가 연결되어 있다는 것을 암시적으로 알 수 있습니다.
예를 들어 (1, 2)는 상(0, 2), 하(2, 2), 좌(1, 1), 우(1, 3)가 연결 되어있다는 것을 말이죠.
저희는 그래프의 값들을 row와 col이라는 변수명을 통해 값들에 접근할 것입니다.
가로를 row로 세로를 col로 생각하는 것입니다. graph[row][col]를 통해 원하는 값에 접근할 수 있게 됩니다. 즉, (2, 3)에 있는 값을 알고 싶으면, graph[2][3]을 통해 알 수 있습니다.
이제 그래프를 구현할 수 있으니, 순회하는 방법을 알아보도록 합시다.
그래프의 순회
그래프의 순회는 트리의 순회와 마찬가지로, 모든 정점을 지나야 합니다. 대표적으로 2가지 방법이 있는데 BFS와 DFS입니다.
Breadth First Search (BFS)
6강에서 배운 트리의 순회인 level order traversal과 매우 유사합니다. 그래프 순회를 할 때, 시작점이 주어질 텐데, 이를 루트 노드라 생각하여, level별로 탐색하는 것이 BFS입니다.
from collections import deque
def bfs(graph, start_v):
visited = [start_v]
queue = deque(start_v)
while queue:
cur_v = queue.popleft()
#해야할일을 여기서 한다
#if cur_v == value:
# return cur_v
for v in graph[cur_v]:
if v not in visited:
visited.append(v)
queue.append(v)
return visited
다음과 같은 그래프를 A에서 시작하여 탐색해 보도록 하겠습니다.
graph = {
"A": ["B"],
"B": ["A", "C", "E"],
"C": ["B", "D"],
"D": ["C", "E", "F"],
"E": ["B", "D", "F"],
"F": ["D", "E"],
}
시작점은 A라고 가정하겠습니다.
—영상 첨부—
BFS의 코드 구현과 작동 원리에 대해서 알아보았습니다. tree의 level order traversal과 상당히 비슷함으로, 이 부분을 잘 공부했다면 큰 어려움 없이 따라서 오셨을 겁니다. BFS 코드는 아주 기본적인 템플릿 코드로서, 머릿속에서 바로바로 구현될 수 있어야 합니다!
Depth First Search (DFS)
DFS는 출발점에 시작해서, 막다른 지점에 도착할 때까지 깊게 이동합니다. 만약 가다가 막히면 다시 그 전 노드로 돌아가고, 또 길이 있으면 깊게 이동하는 식의 과정을 통해 그래프를 순회할 수 있습니다.
예를 들어 다음과 같은 그래프가 있다고 할 때 A부터 순회를 해보도록 해봅시다. 여러분들도 한 번 해보세요!
- 답은 !!?
- A-B-C-D-E-G-H-I-F 입니다.
왜 그런 지 한 번 봐 볼까요?
우선 깊게 깊게 파고들어 D까지 이동합니다. 그 이후로 알파벳 순서를 기준으로 E를 먼저 가도록 합시다.
I까지 간 후 이제 막혀 버렸습니다. 이제 왔던 길을 되찾는 과정을 거칩니다.
H, G, E, D 순으로 올라갑니다.
그 후 아직 탐색하지 않는 F를 방문해 줍니다.
F 이후 마찬가지로 갈 길이 없습니다.
왔던 길인 D, C, B, A 순으로 올라감으로써, 탐색을 마무리합니다.
이제 탐색 방법을 알았으니, DFS 구현을 알아볼 차례입니다. DFS는 스택과 재귀로 구현할 수 있습니다. 저희는 구현이 쉬운 재귀로 구현한 방법을 알아보겠습니다.
visited = []
def dfs(cur_v):
visited.append(cur_v)
for v in graph[cur_v]:
if v not in visited:
dfs(v)
tree의 preorder, inorder, postorder의 순회 방식과 매우 유사합니다.
—영상 첨부—
이런 식으로 DFS의 순회 과정을 알아보았습니다. 재귀에 익숙하지 않으면 이해하기 힘든 과정일 수 있습니다. 하지만 코드 작성 자체는 어렵지 않으므로, 위의 과정을 반복하여, 최종적으로 머릿속에서 그려지는 것이 익숙해지면 좋을 것 같습니다.
BFS와 DFS 시간 복잡도
각각의 순회는 모든 정점$(V)$들을 탐색해야 하고 그러기 위해서는 정점에 연결된 edge$(E)$들을 모두 확인해 봐야 합니다. 따라서 BFS와 DFS 시간 복잡도는 $O(V+E)$입니다.
다익스트라 (Dijkstra) 알고리즘
앞에서 설명한 가중치 그래프에 대해 짤막하게 짚고 넘어갔습니다. 가중치 그래프는 아래와 같이 그래프에 간선(edge)마다 가중치(weight)를 추가한 것입니다. 예를 들어 A에서 B로 가는 데 3의 비용이 든다고 생각하면 됩니다.
이렇게 가중치를 설정하면, 다음과 같은 생각을 할 수 있습니다.
❓ A에서 D로 가는 경로 중 가장 비용이 작게 드는 경로는 뭘까?
가중치가 없는 그래프에서는 모든 그래프의 가중치가 같았기 때문에 A→B→E→D로 가는 경로나 A→B→C→D로 가는 경로의 비용이 같았습니다. 그러나 가중치 그래프에서는 A→B→E→D로 가는 경로가 더 효율적입니다. 왜냐면 총비용이 3+5+3=11로 3+8+2=13보다 작기 때문입니다. 이러한 문제를 해결하기 위해 다익스트라(Dijkstra) 알고리즘을 사용할 수 있습니다.
💡 다익스트라 알고리즘은 가중치 그래프에서 시작점과 도착점이 주어졌을 때, 최소 비용을 반환하는 알고리즘입니다.
다익스트라 알고리즘의 원리
다음과 같이 그래프가 있을 때, 시작점은 A, 도착점은 H라 합시다.
- 각각의 점에 라벨을 매겨 줄 것입니다. 시작점의 라벨은 0으로 초기화하고, 나머지 점들은 $\infty$로 초기화합니다.
- 사용 안 한 라벨 중 제일 작은 라벨을 찾고, 해당 라벨을 사용했다고 표시해 줍니다.
- 해당 점에 인접한 점들의 라벨들을 업데이트해 줍니다. (이미 라벨 되어 있는 값보다 작으면 그 값으로 업데이트해주고, 크면 업데이트하지 않습니다)
- 2-3의 과정을 반복합니다.
- 모든 라벨을 사용했으면 종료합니다.
위 과정이 진행되는 과정을 자세히 보도록 합시다.
다익스트라의 진행
모든 라벨이 업데이트되었으므로, 이제 알고리즘은 종료됩니다. 각 라벨은 A에서 해당 점을 가기 위한 최소 비용입니다. 예를 들어, 위의 예시에서는 A에서 H로 가기 위한 최소 비용은 5입니다.
이제 다익스트라 알고리즘의 진행을 알아보았으니, 구현을 해보도록 합시다.
다익스트라 구현
위의 다익스트라 알고리즘 예시를 코드로 차례차례 구현해 봅시다.
- heapq 불러오기
- import heapq
- 그래프 구현
- graph = { "A": [("B", 2), ("D", 1)], "B": [("C", 2), ("E", 2), ("F", 4)], "C": [("F", 4)], "D": [("G", 5)], "E": [("H", 1)], "F": [("E", 3)], "G": [("F", 7), ("H", 6)], "H": [], }
- distance 구현
# 일반적인 경우 - 노드 자료형 상관없이 사용 가능 distance = {v:float("inf") for v in graph} # 정점이 0 시작하며 연속적인 정수형으로 주어졌을 때 distance = [float("inf")] * len(graph) # 1로 시작하는 일련의 정점이 주어질 경우 distance = [float("inf")] * (len(graph) + 1) - distance 구현은 리스트 혹은 딕셔너리 중에서 선택하시면 됩니다. 다만 정점(vertex 혹은 node)이 문자형으로 주어지는 경우가 종종 발생하기 때문에 아래 예시의 1번째 코드를 보통 사용한다고 보시면 됩니다. 다만, 0~10 혹은 1~9 같이 연속적인 정수형 데이터가 정점으로 주어지면, 인덱스로 접근하는 리스트로도 사용 가능하다는 점도 알고 계시면 좋을 것 같습니다.
- heap 구현
- distance[start] = 0
우선 각 점의 최소 비용을 저장할 리스트(list)가 필요합니다. 위의 진행 과정처럼, 시작점은 0으로, 다른 모든 점을 $\infty$로 라벨을 해줍니다.
distance = {v:float("inf") for v in graph}
distance[start] = 0
또한 탐색할 그래프는 삼중 리스트로 되어있다고 가정을 해봅시다. 예를 들어 2번째 index에는 2번 점과 연결된 [점1, 가중치1], [점2, 가중치2], [점3, 가중치3] $\cdots$으로 저장되어 있습니다.
앞선 진행 과정에서 다음과 같은 질문이 있었습니다.
<aside> ❓ 사용하지 않은 라벨 중에서 가장 작은 것은?
</aside>
이 접근을 사용하기 위해서는 전에 배운 heap이라는 자료구조를 사용할 것입니다. 특히 min heap을 말이죠. 위의 질문은 이제 아래와 같이 변환할 겁니다.
q = []
heapq.heappush(q, (0, start))
# from heapq import heappush를 했다면 heappush로만 사용해도 괜찮습니다.
그렇다면 이제 저희의 목적은 다음 질문에 대한 답을 찾는 것입니다.
<aside> ❓ heap에 있는 라벨 중에서 가장 작은 것은?
</aside>
결론은 heappop() 사용입니다. heappop() 을 사용하게 되면, min heap을 사용했기 때문에, 우선순위(여기서는 라벨)가 제일 작은 원소가 튀어나옵니다. 그리고 heap이 비어있게 될 때까지 이 과정들을 반복합니다. 일련의 과정은 graph에서의 BFS와 상당히 유사합니다.
while q:
dist, now = heapq.heappop(q)
# from heapq import heappop을 했다면, heappop만 사용해도 괜찮습니다.
만약 heap에서 나온 가중치가 distance에 이미 저장되어 있는 값보다 크면, 인접한 점들을 업데이트 해줄 필요가 없습니다.
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
이제 인접한 점들을 업데이트하는 부분입니다. 현재 비용에 인접점의 가중치를 더한 값이 distance에 있는 값보다 작으면 업데이트해 주고 heap에 넣어줍니다. 이 과정을 모든 인접점에 대해 해줍니다.
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for vv, ww in graph[now]:
cost = distance[now] + ww
if cost < distance[vv]:
distance[vv] = cost
heapq.heappush(q, (cost, vv))
heap이 비어있게 되면, 더 이상의 업데이트가 불가능해져, 알고리즘이 종료됩니다. return은 요구사항에 맞게 써주면 됩니다. 여기서는 start에서 end까지의 거리(비용)를 반환하겠습니다.
return distance[end]
모든 과정을 합친 코드는 아래에 있습니다. BFS와 heap의 개념이 잘 잡혀있고, 다익스트라의 구현 과정을 이해했다면 코드에 대한 설명은 어렵지 않을 것입니다. 그럼에도 보는 것과 코드를 직접 짜는 것은 분명히 다른 문제이기 때문에, 여러 번 코드를 짜보고 실전에서 즉각 사용할 수 있도록 하는 것이 좋겠습니다.
import heapq
def dijkstra(graph, start, end):
distance = [float("inf")] * (vertex + 1)
distance[start] = 0
q = []
heapq.heappush(q, (0, start))
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for vv, ww in graph[now]:
cost = distance[now] + ww
if cost < distance[vv]:
distance[vv] = cost
heapq.heappush(q, (cost, vv))
return distance[end]
다음은 실제 코드 동작 상황을 디버깅해 보면서 시각화한 동영상입니다. 동영상 내부와 코드가 일부 다른 점은 존재하지만, 결국 같은 논리이기 때문에 이 점 감안하고 봐주시면 될 것 같습니다.
코딩테스트 활용
코드 템플릿 활용하기
그래프 문제는 위에서 소개된 템플릿 코드를 활용해서 해결하시면 됩니다. 가장 추천해 드리는 방법은 이 템플릿 코드를 외운 다음, 이것을 기본 틀로 해서 아래 주석 처리한 부분을 채워서 사용하시면 될 것 같습니다.
BFS 템플릿 코드
- 기본형 그래프
from collections import deque
def bfs(graph, start_v):
visited = [start_v]
queue = deque(start_v)
while queue:
cur_v = queue.popleft()
# *---------------------------------------*
# 그래프를 방문하며 처리해야할 일을 여기서 한다
# (예시)
# if cur_v == value:
# << 현재 노드가 특정 값을 만족할 때 해야할 일 >>
# return cur_v
# *---------------------------------------*
for v in graph[cur_v]:
visited.append(v)
queue.append(v)
return visited
- 그리드형 그래프
DFS 템플릿 코드
- 기본형 그래프
visited = []
def dfs(cur_v):
# *---------------------------------------*
# 그래프를 방문하며 처리해야할 일을 여기서 한다
# (예시)
# if cur_v == value:
# << 현재 노드가 특정 값을 만족할 때 해야할 일 >>
# return cur_v
# *---------------------------------------*
visited.append(cur_v)
for v in graph[cur_v]:
if v not in visited:
dfs(v)
- 그리드형 그래프
from collections import deque
def bfs(grid):
def isValid(r, c):
return (
(r >= 0 and r < row_len)
and (c >= 0 and c < col_len)
and grid[next_r][next_c] == 1
)
row_len, col_len = len(grid), len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]
dr = [0, 1, 1, 1, 0, -1, -1, -1]
dc = [1, 1, 0, -1, -1, -1, 0, 1]
queue = deque()
queue.append(0, 0)
visited[0][0] = True
while queue:
cur_r, cur_c = queue.popleft()
for i in range(8):
next_r = cur_r + dr[i]
next_c = cur_c + dc[i]
if isValid(next_r, next_c):
if not visited[next_r][next_c]:
queue.append((next_r, next_c))
visited[next_r][next_c] = True
그래프 변환
앞서 설명했듯이 그래프를 표현할 수 있는 방법은 인접 행렬, 인접 리스트, 암시적 그래프가 있습니다. 하지만 코딩 테스트에서는 위와 같은 형태보다는 edge의 집합으로 그래프를 주는 경우가 많습니다. 우리는 이와 같은 edge set 그래프를 우리가 원하는 그래프 표현 방식으로 변환해야 할 필요가 있습니다.
다음과 같은 edge set 그래프를 인접 행렬, 인접 리스트로 변환하는 과정을 보여드리겠습니다.
# num of vertex
n = 6
# edge = [u, v]
edge_set = [[1, 2], [2, 6], [2, 4], [4, 3], [3, 2], [3, 5]]
이때 우리는 이 그래프가 무향그래프인지 방향그래프인지를 파악해야 합니다.
무향 그래프의 경우 변환 코드는 다음과 같습니다.
인접 행렬
graph = [[0 for _ in range(n)] for _ in range(n)]
for u, v in edge_set:
graph[u][v] = 1
graph[v][u] = 1
- 결과
- [0, 1, 0, 0, 0, 0] [1, 0, 1, 1, 0, 1] [0, 1, 0, 1, 1, 0] [0, 1, 1, 0, 0, 0] [0, 0, 1, 0, 0, 0] [0, 1, 0, 0, 0, 0]
인접 리스트
# dict version
graph = {}
for u, v in edge_set:
if u not in graph:
graph[u] = []
graph[u].append(v)
if v not in graph:
graph[v] = []
graph[v].append(u)
# defaultdict version
from collections import defaultdict
graph = defaultdict(list)
for u, v in edge_set:
graph[u].append(v)
graph[v].append(u)
- 결과
- 1 : [2] 2 : [1, 6, 4, 3] 6 : [2] 4 : [2, 3] 3 : [4, 2, 5] 5 : [3]
방향 그래프의 경우 변환 코드는 다음과 같습니다.
인접 행렬
graph = [[0 for _ in range(n)] for _ in range(n)]
for u, v in edge_set:
graph[u][v] = 1
- 결과
- [0, 1, 0, 0, 0, 0] [0, 0, 0, 1, 0, 1] [0, 1, 0, 0, 1, 0] [0, 0, 1, 0, 0, 0] [0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0]
인접 리스트
# dict version
graph = {}
for u, v in edge_set:
if u not in graph:
graph[u] = []
graph[u].append(v)
# defaultdict version
from collections import defaultdict
graph = defaultdict(list)
for u, v in edge_set:
graph[u].append(v)
- 결과
- 1 : [2] 2 : [6, 4] 4 : [3] 3 : [2, 5]
또한 edge set 그래프에 edge의 가중치가 포함된 경우가 있습니다. 주어진 그래프가 방향 가중치 그래프인 경우 변환 코드는 다음과 같습니다.
# num of vertex
n = 6
# edge = [u, v, w]
edge_set = [[1, 2, 4], [2, 6, 1], [2, 4, 2], [4, 3, 3], [3, 2, 2], [3, 5, 1]]
인접 행렬
graph = [[0 for _ in range(n)] for _ in range(n)]
for u, v, w in edge_set:
graph[u][v] = w
- 결과
- [0, 4, 0, 0, 0, 0] [0, 0, 0, 2, 0, 1] [0, 2, 0, 0, 1, 0] [0, 0, 3, 0, 0, 0] [0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0]
인접 리스트
# dict version
graph = {}
for u, v, w in edge_set:
if u not in graph:
graph[u] = []
# 그래프가 변동되지 않는 경우 immutable 객체인 tuple을 사용해도 좋습니다.
graph[u].append([v, w])
# defaultdict version
from collections import defaultdict
graph = defaultdict(list)
for u, v, w in edge_set:
# 그래프가 변동되지 않는 경우 immutable 객체인 tuple을 사용해도 좋습니다.
graph[u].append([v, w])
- 결과
- 1 : [[2, 4]] 2 : [[6, 1], [4, 2]] 4 : [[3, 3]] 3 : [[2, 2], [5, 1]]
visited
딕셔너리(또는 해시셋) 구현
파이썬의 딕셔너리(dictionary)를 통해 visited를 만들 수 있습니다. key값으로 문자, 문자열, 숫자 등의 다양한 형태의 데이터를 담을 수 있고, value값으로 True 혹은 False를 담을 수 있는 불리언 (boolean) 자료형을 지정하여 방문 여부를 체크할 수 있습니다. 아래 코드에서 보면 visited를 dictionary(또는 set)로 구현했기 때문에 방문 체크를 할 때 if ___ not in visited: 를 이용해서 시간복잡도 O(1)으로 구현할 수 있습니다.
def dfs(cur_v, visited):
visited[cur_v] = True
for next_v in graph[cur_v]:
if next_v not in visited:
dfs(next_v, visited)
def bfs(graph, start_v):
q = deque()
visited = {start_v: True}
q.append(start_v)
while q:
cur_v = q.popleft()
print(cur_v)
for next_v in graph[cur_v]:
if next_v not in visited:
visited[next_v] = True
q.append(next_v)
return visited
리스트 구현
딕셔너리뿐만 아니라 리스트로도 visited를 만들 수 있습니다. 리스트는 내재적으로 순서를 고려한 자료형이고, 정수형 인덱스로 빠르게 접근할 수 있다는 것이 큰 특징입니다.
다만 dictionary와 set과는 다르게 방문여부 체크를 할 때 인덱스에 직접 접근해서 판별을 해야 합니다.
ex) if visited[u] == False: 이런식으로 O(1)의 시간복잡도로 체크할 수 있습니다.
# 상황 : 그래프 노드가 1 ~ 10으로 정의된 경우 (연속적으로 존재하는 정수형)/ 또는 그리드형 그래프
visited = [False for i in range(10)]
visited = [[False] * col_len for _ in range(row_len)]
# 방문하지 않은 노드인지 아닌지 검사하기
if visited[u] == False: # O(1)
if value not in visited: # O(n) -> 이렇게 검사하면 안된다!
딕셔너리로 visited 만들기
파이썬의 딕셔너리(dictionary)를 통해 visited를 만들 수 있습니다. key값으로 문자, 문자열, 숫자 등의 다양한 형태의 데이터를 담을 수 있고, value값으로 True 혹은 False를 담을 수 있는 불리언 (boolean) 자료형을 지정하여 방문 여부를 체크할 수 있습니다. 다음 코드는 앞에서 보여드린 가중치 없는 무향 그래프 edge set을 가지고 visited를 만드는 코드입니다.
~~# edge set을 이용하여 visited 만들기
# (예시) 가중치 없는 무향 그래프
edge_set = [[1, 2], [2, 6], [2, 4], [4, 3], [3, 2], [3, 5]]
visited = {}
for u, v in edge_set:
visited[u] = False
visited[v] = False
print(visited)~~
결과- {1: False, 2: False, 6: False, 4: False, 3: False, 5: False}
리스트로 visited 만들기
딕셔너리뿐만 아니라 리스트로도 visited를 만들 수 있습니다. 리스트는 내재적으로 순서를 고려한 자료형이고, 정수형 인덱스로 빠르게 접근할 수 있다는 것이 큰 특징입니다. 2가지 방식으로 리스트를 활용해서 visited를 만들 수 있습니다. 먼저 딕셔너리와 비슷하게 False를 활용한 방식입니다.
~~# 상황 : 그래프 노드가 1 ~ 10으로 정의된 경우 (연속적으로 존재하는 정수형)
visited = [False for i in range(10)]
# 방문하지 않은 노드인지 아닌지 검사하기
if visited[u] == False:
''' 방문하지 않은 노드일 때 해야할 일 '''~~
다만 이렇게 만드는 경우는 그래프의 노드가 정수형이어야 하며, 연속적으로 존재해야 사용할 수 있습니다. 불연속적으로 존재해도 이 방법을 사용할 수는 있지만, 리스트의 장점을 활용하기 어렵고, 필요하지 않은 정수형에 대해서도 정의를 해줘야 하므로 비효율적입니다.
2번째 방식은 visited 리스트에 방문한 노드를 추가하는 방식입니다. 위에서 소개한 BFS 코드에서 visited를 리스트로 만들어서 소개했는데, 그것을 가지고 설명하겠습니다.
~~from collections import deque
def bfs(graph, start_v):
visited = [start_v]
queue = deque(start_v)
while queue:
cur_v = queue.popleft()
# *---------------------------------------*
# 그래프를 방문하며 처리해야할 일을 여기서 한다
# (예시)
# if cur_v == value:
# << 현재 노드가 특정 값을 만족할 때 해야할 일 >>
# return cur_v
# *---------------------------------------*
for v in graph[cur_v]:
visited.append(v)
queue.append(v)
return visited~~
리스트로 visited를 만들 때는 False로 초기화하지 않아도 됩니다. 어차피 그래프를 방문하면서 visited에 한 노드씩 append하기 때문입니다. visited에 들어있지 않은 노드들은 아직 방문하지 않았다는 것을 의미합니다. 이러한 경우에는 노드를 방문할 때 다음과 같은 조건문을 쓸 것입니다.
~~if v not in visited:
''' 방문하지 않은 노드에 대해서 해야할 일 '''~~
<aside> 💡 in 연산자에 따른 시간복잡도 차이
결론적으로 visited를 만드는 방법은 상황에 맞게 선택하시면 됩니다. visited를 False로 구성해서 리스트로 만들었다면, if visited[u] == False: 조건문을 사용했을 때 딕셔너리와 리스트에 대한 시간복잡도는 모두 $O(1)$입니다. 다만 in 연산자로 방문 여부를 확인할 때 시간 복잡도 측면에서 리스트가 좋지 않을 수 있습니다. 아래의 코드로 그 차이를 확인해 봅시다.
</aside>
# 상황 : 그래프 노드가 1 ~ 10일 때, 현재 방문하는 노드는 4 (변수 u : 현재 방문하는 노드)
visited_d = {3:True, 1:True, 7:True, 2:True, 8:True}
visited_l = [3, 1, 7, 2, 8]
u = 4
'''
몇 번의 노드 방문 후
'''
if u not in visited_d: # 시간 복잡도 : O(1)
''' u가 방문하지 않은 노드일 때에 해야할 일 '''
if u not in visited_l: # 시간 복잡도 : O(n)
''' u가 방문하지 않은 노드일 때에 해야할 일 '''
방문한 노드만 저장하는 방식을 사용할 때, 저희는 in 연산자로 visited에 현재 방문하는 노드가 존재하는지를 검사할 것입니다. 이때, 딕셔너리는 시간복잡도가 $O(1)$이지만, 리스트는 처음부터 끝까지 확인해 보는 작업이 필요하기 때문에 $O(n)$의 시간복잡도가 발생합니다. 따라서 이 경우는 리스트보다 딕셔너리를 사용하는 것이 효율적입니다.
1. 코딩테스트에서는 주로 무향 그래프(undirected graph)를 다룹니다.
2. 코딩 테스트에서는 주로 단순 그래프(simple graph)를 다룹니다.
3. 가중치 그래프는 추후 다익스트라 알고리즘에서 쓰입니다. 코딩테스트 입문편에서는 가중치 그래프를 다루지 않으며, 심화편에서 다루도록 하겠습니다.
4. 코딩 테스트에서는 주로, 인접 행렬보다는 인접리스트를 사용합니다.
'코딩테스트 [킬링캠프]' 카테고리의 다른 글
| 2.7 힙 (Heap - Priority queue) (2) | 2024.01.03 |
|---|---|
| 2.6 트리 (Tree) (1) | 2024.01.03 |
| 2.5 이진 탐색 (Binary Search) (1) | 2024.01.03 |
| 2.4 재귀 (Recursion) (1) | 2024.01.03 |
| 2.3 해시테이블 (Hash Table) (1) | 2024.01.03 |