🕯️ 개념
✔️ 인접 행렬 / 인접 리스트
- 인접 행렬 방식 : 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
-
모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다.
-
두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 비교적 빠르다.
INF = 987654321 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ]
-
- 인접 리스트 방식 : 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
-
‘연결 리스트’라는 자료구조 이용 (파이썬에서는 2차원 리스트를 이용하면 된다.)
-
연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.
-
두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. (연결된 데이터를 하나씩 확인해야 하기 때문)
graph = [[] for _ in range(3)] graph[0].append((1, 7)) # 노드 정보 : (노드, 거리) graph[0].append((2, 5)) graph[1].append((0, 7)) graph[2].append((0, 5))
-
✔️ BFS (너비 우선 탐색)
- 너비를 우선하여 그래프를 탐색
- 시작점인 루트 노드와 같은 거리에 있는 노드를 우선으로 방문
- 큐(queue) 자료구조를 사용. 노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보만 큐에 넣어 먼저 큐에 들어있던 노드부터 방문.
collections라이브러리의deque사용하면 시간 절약 가능- 동작 방식
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
✔️ DFS (깊이 우선 탐색)
- 한 방향으로 갈 수 있을 만큼 깊게 탐색
- 갈 수 있는 한 끝까지 탐색해 리프 노드를 방문하고, 이전 갈림길에서 선택하지 않았던 노드를 방문
- 스택(stack) 자료구조를 사용. 먼저 방문한 노드에 연결된 노드보다 현재 방문한 노드에 연결된 노드를 방문해야 한 방향으로 갈 수 있기 때문
- 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
👩💻 코드
✔️ BFS (너비 우선 탐색)
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
graph = # 생략
visited = [False] * 9
bfs(graph, 1, visited)
from collections import deque
def BFS_with_adj_list(graph, root):
visited = []
queue = deque([root])
while queue:
n = queue.popleft()
if n not in visited:
visited.append(n)
queue += graph[n] - set(visited)
return visited
print(BFS_with_adj_list(graph_list, root_node))
✔️ DFS (깊이 우선 탐색)
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = # 생략
visited = [False] * 9
dfs(graph, 1, visited)
def DFS_with_adj_list(graph, root):
visited = []
stack = [root]
while stack:
n = stack.pop()
if n not in visited:
visited.append(n)
stack += graph[n] - set(visited)
return visited
print(BFS_with_adj_list(graph_list, root_node))
⏰ 시간복잡도
✔️ BFS (너비 우선 탐색)
- 인접 행렬로 표현할 경우
- 정점 하나당 for loop을 V만큼 돌기 때문에, O(V) 시간이 필요
- 전체적으로는 모든 정점을 한 번씩 방문할 때마다 O(V)의 시간이 걸리는 for loop가 실행되므로, 전체 시간 복잡도는 V * O(V) =
O(V^2)
- 인접 리스트로 표현할 경우
- BFS는 총 V번 부르게 된다.
- 그러나 인접 행렬과 달리 BFS 하나 당 각 정점에 연결되어 있는 간선의 개수만큼 탐색을 하게 되어 BFS 하나의 수행 시간이 일정하지 않다
- BFS가 다 끝났을 시점에는 모든 정점을 한 번씩 방문하고, 모든 간선을 한 번씩 검사하게 되므로 전체 시간 복잡도는
O(V+E)
✔️ DFS (깊이 우선 탐색)
- 인접 행렬로 표현할 경우
- DFS 하나에 for loop을 V만큼 돌기 때문에, O(V) 시간이 필요
- 정점을 방문할 때마다 DFS를 부르는데, V개의 정점을 모두 방문하므로 전체 시간 복잡도는 V * O(V) =
O(V^2)
- 인접 리스트로 표현할 경우
- DFS는 총 V번 부르게 된다.
- 그러나 인접 행렬과 달리 DFS 하나 당 각 정점에 연결되어 있는 간선의 개수만큼 탐색을 하게 되어 DFS 하나의 수행 시간이 일정하지 않다
- DFS가 다 끝났을 시점에는 모든 정점을 한 번씩 방문하고, 모든 간선을 한 번씩 검사하게 되므로 전체 시간 복잡도는
O(V+E)
👑 예제
from collections import defaultdict
def solution(tickets):
answer = []
routes = defaultdict(list)
for ticket in tickets:
routes[ticket[0]].append(ticket[1])
for key in routes.keys():
routes[key].sort(reverse=True)
stack = ['ICN']
while stack:
tmp = stack[-1]
if not routes[tmp]:
answer.append(stack.pop())
else:
stack.append(routes[tmp].pop())
answer.reverse()
return answer{ 시작점 : [도착점], ... }형태의인접 리스트그래프를 생성- ‘도착점’의 리스트를 정렬 (알파벳 역순서로)
DFS 알고리즘을 사용해 모든 점을 순회 (스택이 빌때까지) (도착점부터 역순으로 찾음)- 스택에서 가장 위 데이터를 가져온다
- 가져온 데이터가 그래프에 없거나 티켓을 모두 사용한 경우 path에 저장
- 아니라면, 가져온 데이터를 시작점으로 하는 도착점 데이터 중 가장 마지막(알파벳 순) 데이터를 가져와 스택에 저장
- path를 역순으로 출력
from collections import deque
def solution(n, computers):
answer = 0
visited = [0] * n
for i in range(n):
if visited[i]:
continue
answer += 1
dq = deque([computers[i]])
while dq:
nodes = dq.popleft()
for j in range(n):
if nodes[j] and not visited[j]:
dq.append(computers[j])
visited[j] = 1
return answer- 0번째 컴퓨터부터 시작해서 이와 직/간접적으로 연결되어 있는 모든 컴퓨터들 방문
- 이후에도 아직 방문하지 않은 컴퓨터가 있으면 answer를 하나씩 증가시키고, 방문하지 않은 컴퓨터 중 번호가 가장 작은 것에서부터 시작해 다시 dfs를 호출
- 모든 컴퓨터를 방문하면 반복을 종료하고 answer를 반환
[참고]
https://cyc1am3n.github.io/2019/04/26/bfs_dfs_with_python.html
https://velog.io/@kjh107704/그래프-BFS와-DFS
DCDI