오늘 배운 것들

1. 다익스트라 알고리즘

양의 가중치를 갖는 그래프에서 출발 노드로부터 최단거리를 찾는 알고리즘.
임의의 노드까지의 최단거리만 찾으면 되는 경우라면 중간에 정지하도록 구성할 수도 있다.

1-1. 작동방식

0. 각 노드로의 최단 거리를 저장할 리스트(최단거리리스트)를 만들고 INF로 초기화한다.
1. 출발 노드가 현재 노드가 된다.
2. 현재 노드로부터 방문할 수 있는 인접노드들까지의 거리를 계산한다.
   인접노드의 거리 = 현재 노드까지의 거리 + 현재 노드에서 인접노드까지의 거리
3. 계산한 거리가 최단거리가 되는 노드들을 최단거리리스트에 갱신한다.
4. 현재 노드를 방문한 노드로 표시한다.
5. 방문하지 않은 노드가 있다면 그중 최단 거리인 노드(우선순위 큐)를 현재 노드로 하고 2로 돌아간다.
6. 모두 방문했다면 종료

알고리즘 종료 후 최단거리리스트에 저장된 값들이 출발 노드로부터의 최단거리가 된다.
만약 목적지 노드를 지정하고 싶다면

5. 목적지 노드를 방문하지 않았다면 방문하지 않은 노드 중 최단 거리인 노드를 현재 노드로 하고 2로 돌아간다.
6. 목적지 노드를 방문했다면 종료

로 바꾸면 된다.
단 알고리즘 종료 후 최단거리리스트에 저장된 값들 중 방문한 노드의 값만이 최단거리를 보장한다.
최단거리리스트에 경로도 저장하게 한다면 최단경로 또한 구할 수 있다.

아래는 다익스트라 알고리즘을 공부 후 들었던 의문을 정리해보았다.

1-2. 왜 최단거리를 보장하는가(그리디 알고리즘)

그리디(탐욕) 알고리즘은 지금 당장 최적인 해를 선택해가며 결과를 만들어내는 알고리즘을 말한다.
그러나 그리디 알고리즘이 언제나 최적해를 보장하는 것은 아니다.

다익스트라 알고리즘에서는 매번 최단거리인 노드를 선택하여 방문한다.
모든 가중치는 양의 값을 가지기 때문에 현재 최단 거리로 방문할 수 있는 노드를 방문하면 그것이 최단거리가 된다.
다른 곳을 거쳐 간다면 무조건 비용이 늘어난다.

1. 양의 가중치를 가지기 때문에
2. 현재 최소 비용인 노드를 방문하는 것이 최적해의 일부이다.

는 조건이 있기에 그리디 알고리즘이 사용될 수 있는 것이다.

시야가 좁아진 상황에서는 미시적인 최적을 선택하게되는 순간이 온다.
그러나 우리는 그것이 결과적으로 최적이 아니었던 경험을 많이 해왔다. (경제학에서의 동적 비일관성)
순간의 최적은 전체에서의 최적을 보장하지 않는다.
전역 최적해에 도달하기 위해서는 전체를 보아야 한다.

순간 최적을 선택하지 못 했더라도 전역 최적해에 도달하는 데에 문제가 없는 경우 또한 많다.

1-3. 왜 효율적인가(다이나믹 프로그래밍)

왜 모든 경로를 탐색하는 경우보다 다익스트라 알고리즘이 효율적인 이유는 방문한 노드를 다시 방문하지 않기 때문이다.
여기서 방문은 해당 노드를 거쳐 갈 수 있는 모든 경우를 계산했다는 의미이다.
1-2에서 처럼 방문한 노드는 그 순간 최단 거리가 확정되기 때문에 다시 방문할 필요가 없다.
다른 노드를 거쳐 다시 돌아오는 경우의 수를 고려할 필요가 없기 때문에 연산량이 줄어든다.

2. 푼 문제

2-1. 트리의 부모 찾기(백준 11725)

from queue import Queue
import sys
input = sys.stdin.readline

def main() -> None:
    N = int(input())
    A = [list(map(int, i.split())) for i in sys.stdin]
    D = {i: [] for i in range(1, N+1)}
    for i, a in enumerate(A):
        D[a[0]].append(i)
        D[a[1]].append(i)
    q = Queue()
    q.put(1)
    parent_list = [None for _ in range(N)]
    parent_list[0] = 0
    while not q.empty():
        now = q.get()
        for i in D[now]:
            a = A[i]
            if len(a) > 1 and now in a:
                a.remove(now)
                parent_list[a[0]-1] = now
                q.put(a[0])
    print(*parent_list[1:], sep="\n")
    
main()

트리를 구현해서 풀까 하다가 트리 구현문제를 한 번 더 푸는 것 같아 큐로 구현해 보았다.
루트 노드로 부터 레벨을 내려오며 자식 노드를 찾는 구조인데
더 효율적으로 만들 수 있을 것 같지만 떠오르지 않아 일단 여기까지.