
# 그래프 형태:    [1]---7---[0]---5---[2]
# 노드: [0],[1],[2] // 비용: 5,7

#===================================================================#
# 1. 인접 행렬: 2차원 배열에 각 노드가 연결된 형태 기록함 

INF = 999999999 # 무한대-> 연결 안되어있다는 뜻
# 2차원 리스트 -> 인접 행렬
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]   # 현재 노드는 0으로 표시, 연결된 노드는 간선 비용으로 표시, 연결안된 노드는 INF로 표시
]
print(graph)

#===================================================================#

# 2. 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식

# 행(Row)이 3개인 2차원 리스트 -> 인접 리스트
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))
# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0, 7))
# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0, 5))
print(graph)

#===================================================================#

# 메모리 : 인접리스트가 효율적 (인접행렬은 모든 관계 저장하므로 노드 많을수록 bad)
# 속도   : 인접리스트가 느림   (위의 이유로 연결된 데이터 하나씩 확인해야해서 느림)

# ex) 노드 1과 노드 7 연결 확인 
# 인접행렬 (graph[1][7]만 확인) vs 인접리스트 (노드 1에 대한 인접리스트 앞에서부터 차례대로 확인 필요)

# => 특정 노드와 연결된 모든 인접노드 순회해야 할 경우, '인접리스트'방식이 메모리 효율적!