3주차 WIL[그래프, BFS, DFS, 트리]{미완성}

그래프

정점과 간선으로 이루어진 자료구조로 정점간의 관계를 표현한다.

• 다익스트라

: 그래프의 한 시작점으로부터 임의의 정점까지 최단경로를 탐색하는 알고리즘이다. 간선이 음의 값일 때 사용할 수 없다.

→ 힙을 사용해 간선정보를 저장하고, 현재 노드에서 그리디하게 최소가 되는 원소를 추가해 탐색범위를 넓혀간다.

from heapq import heappush, heappop
from collections import defaultdict

n = 10
graph = defaultdict(list)
answer = float('inf')
def dijkstra(start, end):
    q = []
    heappush(q, (0, start))
    distance = [float('inf')] * (n + 1)
    while q:
        dist, now = heappop(q)
        if dist > answer:
            return float('inf')
        if now == end:
            return dist
        for next_node, weight in graph[now]:
            cost = dist + weight
            if cost < distance[next_node]:
                distance[next_node] = cost
                heappush(q,(cost, next_node))
    return float('inf')

DFS

깊이 우선 탐색으로

1. 뻗어 나가는 브랜치의 수 == 재귀의 수
2. 종료 조건과 시작 조건은 level로 생각하고
3. 자신에 대한 정보를 자식 혹은 부모에게 보낼 것은 매개변수(파라미터) 안에 저장하여 전송한다.
   

위 그림에 해당하는 내용을 너무나 잘 설명을 들은 후 깊이 우선 탐색을 이해하게 되었다.

우선 level의 끝까지 이동 후 다음 실행되지 않은 node들로 향하며 중간에 조건을 넣어 실행하지 않을 재귀를 호출하던지 혹은 idx 등의 정보를 넘겨 for문을 제한하는 형태로 문제를 풀이할 수 있다.