🍕 그래프
그래프는 정점과 간선으로 이루어져야 된다.
만약 간선, 정점 둘 중 하나라도 존재하지 않으면 그래프라고 볼 수 없음
그래프 왜 사용?
어떤 특정 상황에서 대부분 상황을 표현할 수 있으니깐.
그래프 표현 방법
1. 인접 리스트
노드의 개수만큼의 공간을 확보한 뒤에 각 노드를 기준으로 연결된 노드를 저장하는 방식
-> 예를 들어 음 노드 4개가 있으면 대충 이런느낌
graph = [[] for _ in range(4)
# 노드 0은 노드 1과 노드2와 인접하다는 가정
graph[0].append(1)
graph[0].append(2)
# 노드 1은 노드 3과 인접하다는 가정
graph[1].append(3)
# 노드 2가 인접한 것
graph[2].append(3)
# 노드 3이 인접한 것
graph[3].append(0)만약 양방향 그래프면 각 노드에 각각 추가하면 된다. 예를 들어 노드 0과 노드 2 가 양방향 그래프로 연결되어 있으면
graph[0].append(2)
graph[2].append(0)만약 가중치 그래프라면 노드 0과 노드 2 사이의 가중치가 3이라면 뒤에 가중치를 추가해주면 된다.
graph[0].append(([2, 3]))
graph[2].append(([0, 3]))2. 인접 행렬
'노드의 개수 * 노드의 개수' 만큼의 행렬 공간을 만든 후에 간선을 표현하는 방식
3. 간선 리스트
간선의 정보만을 표현하는 방식으로 간선에 대한 정보만(노드 2개로 표현)을 저장하는 방식
-> 근데 거의 인접리스트만 사용함 가끔 인접 행렬? 간선리스트 사용 잘안함
간선 종류 -> 방향 그래프 / 양방향 그래프 / 가중 그래프
말 그대로 방향 존재 유무에 따라 방향, 양방향 그래프가 존재하고 가중 그래프는 노드 사이의 간선에 가중치가 값?이 들어가있는 느낌임
선형 자료구조 vs 비선형 자료구조
선형 자료구조는 배열과 같이 원소들을 하나씩 순차적으로 나열시킨 형태이다. 비선형 자료구조는 반면 하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 형태로 1:N, N:N의 관계를 나타낸다. 그럼 트리와 그래프는? --> 당연히 비선형 자료구조이다.
그래프 문제?
1. 그래프 순회 / 탐색할 땐? -> BFS / DFS
- 그래프 순회는 그래프 내의 모든 노드를 한 번씩 살펴보는 것
- 그러면 노드 수 N, 간선 수 M이라고 하면 시간복잡도는 O(N+M)이 된다.
- 비선형 자료구조이니깐 그래프에서 순회=탐색을 할 때는 시작노드를 설정해 주어야 한다. 이후에 시작노드를 기준으로 연결된 노드들을 살펴보며 그래프를 탐색해야 한다.
- 간선 1개 = 노드 2개이니까 간선은 {시작 노드, 도착 노드}로 표현 가능하니깐 노드의 개수가 N이면 간선의 개수는 최대 시작 노드로 가능 한 것은 N개, 도착 노드로 가능 한 것은 총 노드 개수에서 시작 노드를 제외한 N-1이니깐 N(N-1)가 된다.
- 그럼 시작노드를 기준으로 살펴보는 방식에 따라 DFS / BFS 둘 중 고르면 된다.
1-1) DFS 깊이우선탐색
현재 탐색 중인 노드를 기준으로 연결된 노드를 즉시 방문하는 방식
N = 5
def dfs(node):
# Base case
if visited[node]:
return
visited[node] = True
print(node, end=" ")
# Recursive case
for next_node in graph[node]:
dfs(next_node)
graph = [[] for _ in range(N)]
visited = [False] * N
graph[0].append(1); graph[0].append(2)
graph[1].append(4); graph[1].append(3)
graph[2].append(3)
graph[3].append(0)
dfs(0)1-2) BFS 너비우선탐색
시작노드를 기준으로 거리가 가까운 노드를 먼저 방문하는 방식 => '거리가 가깝다'라는 의미는 시작노드에서 해당 노드까지 갈 때 거친 간선의 개수가 적다는 것을 의미한다.
- 시작 거리와 가까운 곳부터 탐색
- 가까운 것이 먼저 들어가서 가장 먼저 나와야 하므로 스택이 아닌 큐를 사용해야됨.
- 음 쉽게 말해 시작 거리랑 가까운 것부터 차례대로 탐색한다
- 당연한 말이지만 시작 노드로부터 거리가 1인 노드와 연결된 노드가 시작 노드로부터 거리가 2인 노드가 되고 시작 노드로부터 거리가 2인 노드와 연결된 노드가 시작 노드로부터 거리가 3인 노드가 되는 것
- 시작 노드로부터 거리가 k인 노드 <= 시작노드로부터 거리가 k-1인 노드와 연결된 노드들
- 가중그래프가 아닌 경우: 시작 노드로부터 떨어진 간선의 개수 = 시작 노드로부터 떨어진 거리
from collections import deque
N = 5
def bfs(node):
global visited, graph
queue = deque([node])
visited[node] = True
while queue:
node = queue.popleft()
print(node, end=" ")
for next_node in graph[node]:
if not visited[next_node]:
visited[next_node] = True
queue.append(next_node)
graph = [[] for _ in range(N)]
visited = [False] * N
graph[0].append(1); graph[0].append(2)
graph[1].append(4); graph[1].append(3)
graph[2].append(3)
graph[3].append(0)
bfs(0)결론은 BFS / DFS 둘 중 그래프 순회할 때는 자신있는 알고리즘을 사용하면 된다. 근데 만약 시작노드로부터 거리가 가까운 순으로 탐색해야 하는 경우라면 BFS를 사용하는 게 좋음. 그런 경우가 아닐 땐 DFS를 사용하는 편이다.
일반적인 그래프 탐색을 할 때는 둘 중 아무거나 사용해도 되지만, 앞서 언급한대로시작노드로부터 가까운 노드 순으로 방문해야 될 때는 DFS를 사용할 수 없다.
즉, BFS는 간선의 가중치가 없는(=간선의 가중치가 모두 동일한) 그래프에서의 최단 경로 알고리즘으로 활용할 수 있다.
반면, 간선의 가중치가 존재하는 경우에는 다익스트라, 벨만포드, 플로이드 워셜과 같은 최단경로 알고리즘을 사용해야 한다.
그래프 연결 요소 구하기
N = 7
def dfs(node):
global visited, graph, node_set
# Base case
if visited[node]:
return
visited[node] = True
node_set.add(node)
# Recursive case
for next_node in graph[node]:
dfs(next_node)
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)
graph[1].append(5); graph[5].append(1)
graph[1].append(3); graph[3].append(1)
graph[3].append(7); graph[7].append(3)
graph[4].append(6); graph[6].append(4)
count = 0
connect_components = []
for node in range(1, N+1):
node_set = set()
if not visited[node]:
dfs(node)
count += 1
connect_components.append(node_set)
print(count) # 7
print(connect_components) # [{1, 3, 5, 7}, {2}, {4, 6}]기본 문제풀이 BOJ 2606
N = int(input())
M = int(input())
visited = [False] * (N+1)
graph = [[] for _ in range(N+1)]
result = -1
for _ in range(M):
start, end = map(int,input().split())
graph[start].append(end)
graph[end].append(start)
def solution():
global result
dfs(1)
print(result)
def dfs(node):
global visited, graph, result
# Base case
if visited[node]:
return
visited[node] = True
result += 1
# Recursive case
for next_node in graph[node]:
if not visited[next_node]:
dfs(next_node)
solution()3. 사이클이 없는 방향 그래프 DAG -> 위상정렬
4. 최소신장트리 MST -> 프림 알고리즘, 크루스칼 알고리즘
0개의 댓글
