[알고리즘] 9주차 트리, 최단 경로

nerry·2022년 3월 10일

DPT 알고리즘

알고리즘

목록 보기

54/86

트리

정점과 간선을 이용해 사이클이 이루어지지 않게 구성된 자료 구조

특징

계층 모델
비순환 그래프
트리 내에 하위 트리가 있는 재귀적 자료구조
노드 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])

좋아요공감
공유하기글 요소

최소힙

import heapq
import sys

input = sys.stdin.readline # 빠른 입력
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 최단거리 테이블
distance = [INF]*(n+1)

# 노드 연결정보
graph = [[] for i in range(n+1)]

for _ in range(m):
  # a번노드에서 b번 노드로 가는 비용c
  a,b,c = map(int, input().split())
  graph[a].append((b,c))

# 다익스트라 알고리즘(최소힙 이용))
def dijkstra(start):
  q=[]
  # 시작 노드
  heapq.heappush(q, (0,start))
  distance[start] = 0

  while q:
    # 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
    dist, now = heapq.heappop(q)

    # 이미 처리된 노드였다면 무시
    # 별도의 visited 테이블이 필요없이, 최단거리테이블을 이용해 방문여부 확인
    if distance[now] < dist:
      continue
    # 선택된 노드와 인접한 노드를 확인
    for i in graph[now]:
      cost = dist + i[1]
      # 선택된 노드를 거쳐서 이동하는 것이 더 빠른 경우
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost,i[0]))
  
# 다익스트라 알고리즘수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
  # 도달할 수 없는 경우
  if distance[i] == INF:
    print("infinity")
  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])

구현

자료구조 생성, 초기화
1. INF 값 설정
  INF = 노드개수 * 최대가중치 +1
  
  INF 값은?
  INF = 노드개수 * 최대가중치 +1
  ⬇️
  1~N모드에서 모든 노드로 최대가중치로 이동하는 경우 - 자기자신으로 이동하는 경우 보다 큰 값으로 잡아야 버틸 수 있음. 위의 식은 안전한 값을 공식화 한 것
  DONT DO THIS
  1.INF = sys.maxsize : 연산에 시간이 오래걸려서 시간초과 발생 가능
  2. int(1e9) : 극단적인 케이스에서 버틸 수 없음
2. 최단거리 테이블 전체를 INF 로 초기화
  arr = [[INF j in range(n)] for i in range(n)]
3. 자기 자신으로 향하는 비용은 0으로 초기화
4. a→b, b→a 로의 비용 입력

메인 로직

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))

[참고]

nerry

터벅터벅 개발(은좋은)자 로그

이전 포스트

[BOJ] 1300

다음 포스트