[알고리즘] DFS-인접 행렬과 인접 리스트

DFS(Depth-First Search)

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

• 노드 Node (=정점)
• 간선 Edge

노드를 도시, 간선을 도로라고 생각하면,
A라는 도시(노드)에서 B라는 도시(노드)로 이동하기 위해, A와 B를 연결하는 도로(간선)를 거친다고 이해하면 쉽다.

다음 그래프를 크게 2개의 방식으로 표현할 수 있다.

1. 인접 행렬(Adjacency Matrix)

• 2차원 배열에 각 노트가 연결된 형태를 표현하는 방식
  

INF = 99999999 
# 무한의 비용 선언
# 실제 코드에서 논리적으로 정답이 될수 없는 큰값 중에서
999999999, 987654321 등의 값으로 초기화하는 경우 많음.

graph = [
  [0, 7, 5],
  [7, 0, INF],
  [5, INF, 0],
]

print(graph)

2. 인접 리스트(Adjacency List)

모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장

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)

인접 행렬	인접 리스트
모든 관계를 저장하므로 메모리가 불필요하게 낭비된다.	연결된 정보만을 저장하기 때문에 메모리가 효율적으로 관리된다.
테스트1	테스트2
테스트1	테스트2