BFS와 다익스트라

• BFS: 가중치가 동일한 그래프에서 최단 경로 탐색
• 다익스트라: 가중치가 다른 그래프에서 최적의 경로 탐색

백준 1753 - 최단경로 문제는 가중치가 다른 그래프에서 최적의 경로를 찾는 문제입니다. 겉보기엔 BFS로 풀 수 있을 것 같지만, 시간 초과와 메모리 초과를 피하려면 다익스트라 알고리즘을 사용해야 합니다.

• 메모리 초과: 정점이 2만 개인데 인접 행렬을 사용하면 2만 × 2만 배열 크기에서 메모리 초과 발생
  👉 인접 행렬 → 인접 리스트 사용해야함
• 시간 초과: 간선이 30만개인데 queue를 사용하면 가중치를 고려하지 않고 가까운 거리부터 탐색하므로 시간 초과 발생
  👉 queue → priority_queue 사용해야함

⚠️ "BFS처럼 하면 다익스트라도 풀 수 있을 것 같아!"

• 일부 테스트케이스는 통과할 수 있지만, 결국 시간 초과가 발생
• BFS처럼 vis, dist 대신 cost 배열을 갱신하여 최단 경로를 구할 수 있지만, 그래프 표현과 탐색 자료구조를 변경해야 합니다.

인접 행렬 대신 인접 리스트

• 인접 행렬은 O(V^2) 크기의 배열을 사용해 메모리 초과가 발생할 수 있습니다. 인접 리스트는 O(E)크기의 배열을 사용해 간선만 저장합니다.

  // 인접 행렬
  vector<vector<int>> adj; // adj[x][y] = cost;

  // 인접 리스트
  vector<pair<int, int>> adj[MAX]; // adj[x] = {cost, y};

Q. {cost, y}로 저장하는 이유는?
A. priority_queue에서 비용 기준으로 우선순위를 정하기 위함

queue 대신 priority_queue

• 가중치가 있는 그래프에서는 queue 대신 priority_queue를 사용해야 합니다.
• 비용을 우선으로 탐색하기 위해 pair<int, int> 형태로 (비용, 정점)을 저장합니다.
  • {비용, 정점}을 넣으면 비용이 우선순위로 처리

// priority_queue 사용 시 비용 우선
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

greater<pair<int, int>>를 사용하면 비용이 작은 순서대로 꺼내집니다. (== 최소힙)