[알고리즘] 9주차 트리, 최단 경로
트리
정점과 간선을 이용해 사이클이 이루어지지 않게 구성된 자료 구조
특징
- 계층 모델
- 비순환 그래프
- 트리 내에 하위 트리가 있는 재귀적 자료구조
- 노드 N이면 트리는 N-1개 간선을 가짐
- Pre-oreder, In-order, Post-order
- 이진 트리, 이진 탐색 트리, 균형 트리, 이진 힙
용어
- Node : 데이터를 저장하는 기본 요소 (연결된 노드에 대한 간선 정보도 포함)
- Root Node : 트리 맨 위에 있는 노드
- Level : 노드의 깊이
- Parent node, Child node
- Leaf node (Terminal node) : child가 하나도 없는 노드
- Sibling : 동일한 Parent
- Depth : 트리에서 node가 가질 수 있는 최대 level
응용
이진 트리
노드의 최대 branch가 2인 트리
이진 탐색 트리 BST
- 이진 트리 + 추가적인 조건
- 조건 : 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음
- 용도 : 데이터 검색
- 특징
- 장점: 탐색 속도 개선할 수 있음
- 단점
- 노드 삭제가 어려움.
- 평균 시간 복잡도는 O(logn)이지만, 트리가 균형잡히지 않으면 O(n)으로 연결 리스트와 동일한 성능을 보인다.
그래프와 차이
최단 경로 탐색 알고리즘 Shortest Path
다익스트라 알고리즘
- 다이나믹 프로그래밍을 활용한 대표적인 최단경로 탐색 알고리즘
- 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다. (단, 음의 간선은 포함 불가)
- 왜 다이나믹 프로그래밍인가?
최단 거리는 여러 개의 최단 거리로 이루어져있기 때문에
즉, 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용
작동
최단 거리는 여러 개의 최단 거리로 이루어져있기 때문에
즉, 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용
현재까지 알고 있던 최단 경로를 계속해서 갱신
- 출발 노드를 설정합니다.
- 출발 노드를 기준으로 각 노드의 최소 비용을 저장합니다.
- 방문하지 않는 노드 중에서 가장 비용이 적은 노드를 선택합니다.
- 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신합니다.
- 3~4번을 반복
그래프는 실제로 컴퓨터 안에서 처리할 때 이차원 배열 형태로 처리해야 한다.
해당 표는 특정 행에서 열로 가는 비용! 을 뜻함
코드
최소 비용을 찾을 때, 탐색은 힙 구조를 활용해야 선형 탐색(O(n^2))보다 빠른 O(N*logN)으로 진행할 수 있다.
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
# 주어지는 그래프 정보 담는 N개 길이의 리스트
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1) # 방문처리 기록용
distance = [INF] * (n+1) # 거리 테이블용
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
# 방문하지 않은 노드이면서 시작노드와 최단거리인 노드 반환
def get_smallest_node():
min_value = INF
index = 0
for i in range(1, n+1):
if not visited[i] and distance[i] < min_value:
min_value = distance[i]
index = i
return index
# 다익스트라 알고리즘
def dijkstra(start):
# 시작노드 -> 시작노드 거리 계산 및 방문처리
distance[start] = 0
visited[start] = True
# 시작노드의 인접한 노드들에 대해 최단거리 계산
for i in graph[start]:
distance[i[0]] = i[1]
# 시작노드 제외한 n-1개의 다른 노드들 처리
for _ in range(n-1):
now = get_smallest_node() # 방문X 면서 시작노드와 최단거리인 노드 반환
visited[now] = True # 해당 노드 방문처리
# 해당 노드의 인접한 노드들 간의 거리 계산
for next in graph[now]:
cost = distance[now] + next[1] # 시작->now 거리 + now->now의 인접노드 거리
if cost < distance[next[0]]: # cost < 시작->now의 인접노드 다이렉트 거리
distance[next[0]] = cost
dijkstra(start)
for i in range(1, n+1):
if distance[i] == INF:
print('도달 할 수 없음')
else:
print(distance[i])
좋아요공감
공유하기글 요소
플로이드 워셜 알고리즘
시작노드를 1개만 설정하는 것이 아닌 다수 즉, 모든 노드에서 모든 노드까지의 최단 거리를 구하는 방법
- 다익스트라는 시작 노드 1개만 지정하고 다른 노드까지의 최단 거리를 구하는 법
특징
- 양방향이면서 음/양 가중치 그래프에서 최단 경로 찾기
- 모든 노드에서 다른 모든 노드까지의 최단 경로의 길이 꼐산
- 노드 개수가 500개 이하
- 다이나믹 프로그래밍 적용 : 최단 거리를 갱신할 때 점화식을 사용한다는 점
점화식 :
D[a][b] = min(D[a][b],D[a][k]+D[k][b])
- 다익스트라 알고리즘처럼 단계마다 탐색하는 노드 즉, 거쳐가는 노드를 기준으로 알고리즘 수행함.
다만, 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾을 필요가 없다. 왜냐하면 시작 노드가 여러 개이기 때문이다.시간 복잡도 : 매 단계마다 O(n^2) 연산 수행 ➡️ 총 시간 복잡도 O(n^3)
동작
-
노드와 간선 사이 정보를 2차원 리스트 형태의 거리 테이블에 갱신
-
0번부터 n-1번까지 확인하면서 거리 테이블 갱신한다.
for k in range(n): for i in range(n): for j in range(n): graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
구현
-
자료구조 생성, 초기화
- INF 값 설정
INF = 노드개수 * 최대가중치 +1
INF 값은?
INF = 노드개수 * 최대가중치 +1
⬇️
1~N모드에서 모든 노드로 최대가중치로 이동하는 경우 - 자기자신으로 이동하는 경우 보다 큰 값으로 잡아야 버틸 수 있음. 위의 식은 안전한 값을 공식화 한 것
DONT DO THIS
1.INF = sys.maxsize : 연산에 시간이 오래걸려서 시간초과 발생 가능
2. int(1e9) : 극단적인 케이스에서 버틸 수 없음 - 최단거리 테이블 전체를 INF 로 초기화
arr = [[INF j in range(n)] for i in range(n)]
- 자기 자신으로 향하는 비용은 0으로 초기화
- a→b, b→a 로의 비용 입력
- INF 값 설정
-
메인 로직
- 3중 포문 수행하며 DP테이블(arr) 갱신
for k in range(n): for i in range(n): for j in range(n): arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]) ```
코드
import sys
INF = int(1e9)
n = int(input())
m = int(input())
# 2차원 거리테이블 리스트 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]
# 자신의 노드간의 거리는 0으로 변경
for i in range(1, n+1):
for j in range(1, n+1):
if i == j:
graph[i][j] = 0
# 주어지는 그래프 정보 입력
for _ in range(m):
# a -> b로 가는 비용은 c
a, b, c = map(int, input().split())
graph[a][b] = c
# k=거쳐가는 노드
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
for i in range(1, n+1):
for j in range(1, n+1):
if graph[i][j] == INF:
print('도달할 수 없음', end=' ')
else:
print(graph[i][j], end=' ')
print()
벨만 포드 알고리즘
시작 정점으로부터 다른 정점까지의 최단 경로를 찾기 위한 알고리즘
특징
- 음수 가중치가 있는 그래프의 시작 정점에서 다른 정점까지의 최단 거리를 구할 수 있다.
- 음수 사이클 존재 여부를 알 수 있다.
이 안에서 무한으로 뺑뺑이 도는 경우를 알 수 있는 방법은 그래프 정점 개수가 V라고 할 때- 인접 간선을 검사하고 거리 값을 갱신하는 과정을 V-1번으로 제한하면 가능해진다. V 번째 간선이 추가되는 순간 사이클이라고 판단 할 수 있다.
- 시간 복잡도는 O(VE)이다.
동작
- 시작 정점을 결정한다.
- 시작 정점에서 각각 다른 정점까지의 거리 값을 무한대로 초기화한다. (1차원 배열로)
- 현재 정점에서 모든 인접 정점을 탐색하여 기존 저장돼있는 인접 정점까지의 거리보다 현재 정점을 거쳐 인접 정점에 도달하는 거리가 더 짧을 경우 그걸로 갱신 - 매 반복마다 모든 간선 확인 (다익스트라와의 차이)
- 3의 과정을 V-1번 반복
- 위 과정을 모두 마치고 난 후 거리가 갱신된다면 그래프에 음수 사이클이 존재함
코드
INF = float('inf')
V, E = map(int, input().split())
edges = []
for _ in range(E):
s, d, w = map(int, input().split())
edges.append((s, d, w))
def bellman-ford(start):
dist = [INF] * (V + 1)
dist[start] = 0
for i in range(V):
for s, d, w in edges:
if dist[s] != INF and dist[d] > dist[s] + w:
if i == V - 1: # i가 v-1이면 v번째 간선 추가이므로 음수 사이클
return -1
dist[d] = dist[s] + w
return dist
print(bellman-ford(0))
[참고]
- https://techblog-history-younghunjo1.tistory.com/247
- https://m.blog.naver.com/ndb796/221234424646
- https://11001.tistory.com/154
- https://techblog-history-younghunjo1.tistory.com/249
- https://velog.io/@younge/Python-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
- https://8iggy.tistory.com/153
Author And Source
이 문제에 관하여([알고리즘] 9주차 트리, 최단 경로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kinnyeri/알고리즘-9주차-트리-최단-경로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)