🤮1753번. 최단 경로 _ 다익스트라.

우선순위큐

: 기본형은 top에 가장 큰값이 온다.
-> less로 되어 있다. bool operator<(const Node& ) const

• 지금의 다익스트라의 경우 구조체 Node의 value 값이 낮은 것이 top에 오게 해야 한다.
  -> 그래서 우리는 이렇게 사용해야 한다. : greater를 만들자.
  bool operator>(const &Node) const { return value > _obj.value;}

• 호출 부분
  priority_queue<Node, vector Node , greater Node > pq;

다익스트라 접근하기

0) 시작점을 pq에 넣고, 진행하고 pq에는 연결된 노드가 들어간다.
1) 거쳐서 가는 최소값을 기록하는 distTable(초기값은 10e9)
2) 그리디 이기 때문에 visited 변수 필요 없다.
3) pq의 경우 , 가장 낮은 값이 나와야 하므로, greater
operator >() const 만들어줘야 한다.
4) 그리고 struct 를 사용할 거니까 ! operator>() const
5) cost 비교할때는 currentNode.cost + targetNode.cost 와 distTable을 비교해야 한다.
비교 하면서 distTable 보다 작지 않다면 continue 하고,
연이어서 pq에 가장 낮은값을 넣자.

---

최근 풀이 : 240519

• 풀이 시간 240518 23:20 ~ 240519 00:15
  : 우선순위큐 struct랑 greater 연산자 만들어서 풀었다.

• 놓친부분
  : 다익스트라는 그리디이기 때문에
  만약에 해당 조건문에 들어오지 않는다면, pq에 push할 필요가 Never! 전혀 없다.
  -> 해당 조건문 정말 중요하다! 해당 조건문을 작성하지 않으면 메모리 초과 오류 발생한다!

#include <iostream>
#include <mutex>  // mutex 를 사용하기 위해 필요
#include <thread>
using namespace std;
#include <vector>
#include <filesystem>
#include <queue>

struct Node
{
	int vNum;
	int dist;

	// 가장 작은값을 우선순위로 해야한다.
	// pq의 디폴트는 내림차순이다. top이 가장 크다. 
	// less 이고

	// greater 함수객체를 만들어야 한다.
	bool operator>(const Node& _obj) const
	{
		return dist > _obj.dist;
	}
};

//11:20~ 
int main()
{
	int v, e;
	cin >> v >> e;

	// 정점번호는 1번부터 v번까지이다. 
	int startNum = 1;
	cin >> startNum;

	// 편향방향으로 진행해야 할듯하다. 왜냐하면
		// 1번 input 5 1 1 이라고 한다면 1이 출력되어야 하는데 INF가 출력됨.
	// 간선의 갯수 e만큼 for문 돌리면서 

	priority_queue<Node, vector<Node>, greater<Node>> pq;

	// 가중치는 10이하라고 한다 .
	// 
	vector<int>distTable(v + 1, 1e9);

	vector<vector<pair<int, int>>> vNum(v + 1);

	int a, b, c;
	for (int i = 0; i < e; ++i)
	{
		// 5번 정점이 1번 정점까지 가는데 dist 비용 1 발생.

		// 무한은 '가' 이라고 하자.
		// dist Table
		// 1  2  3  4  5
		// 0 가 가 가 가 
		// 0  2  3 가 가  1번을 기준 , 그리고 1번 완료
		// 0  2  3 7  가  2번을 기준 , 그리고 2번 완료
		// 0  2  3 7  가  3번을 기준.

		// check 변수 필요.
		// pq에는 다음에 갈 정점의 번호와 dist를 가지고 있자.
		
		
		cin >> a >> b >> c;
		// first는 타겟 정점 , second는 dist
		vNum[a].push_back({b , c});
		
	}

	// startNum을 기준으로 해서 다익스트라 시작! 

	
	pq.push(Node{ startNum, 0 });
	distTable[startNum] = 0;
	while (!pq.empty())
	{
		Node targetNode = pq.top();
		pq.pop();

		int targetNum = targetNode.vNum;
		int targetDist = targetNode.dist;

		// pq에 넣기 전에 .
		// distTable 비교 해야 한다. 


		// 무한은 '가' 이라고 하자.
		// dist Table
		// 1  2  3  4  5
		// 0 가 가 가 가 
		// 0  2  3 가 가  1번을 기준 , 그리고 1번 완료
		// 0  2  3 7  가  2번을 기준 , 그리고 2번 완료
		// 0  2  3 7  가  3번을 기준.
		for (int i = 0; i < vNum[targetNum].size(); ++i)
		{
			int endPoint = vNum[targetNum][i].first;
			int dist = vNum[targetNum][i].second;

			if (targetDist + dist < distTable[endPoint])
			{
				distTable[endPoint] = targetDist + dist;
			}
			// 놓친부분은 이미 if 조건문 속하지 않으면 continue 해야 한다.
			else
			{
				continue;
			}

			pq.push(Node{ endPoint, distTable[endPoint] });
		}
	}

	for (int i = 1; i <= v; ++i)
	{
		if (distTable[i] == 1e9)
		{
			printf("INF\n");
		}
		else
			printf("%d\n", distTable[i]);
	}

}

---

최근 풀이 : 240106

#include <iostream>
using namespace std;
#include <string>

#include <vector>
#include <limits.h>
#include <algorithm>
#include <map>
#include <future>
#include <thread>
#include <numeric>
#include <stack>
#include <queue>
#include <memory>
#include <set>
#include <string>
#include <stack>
#include <mutex>



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int vertex, edge;
	cin >> vertex >> edge;

	int start;
	cin >> start;

	int u, v, w;
	// u 에서 v로 가는 가중치가 w인 간선.
	// 5번에서 1로 가는 가중치는 1
	//[5][1] = 1;
	// [타겟 정점 번호 : 5] = {비용, 향하는 정점.}

	vector<vector<pair<int, int>>> path(vertex + 1);
	for (int i = 0; i < edge; ++i)
	{
		cin >> u >> v >> w;
		// 넣을 때부터 음값으로 넣는 것이 아니라,
		// pq에 넣을 때 음값으로 넣자...
		path[u].push_back({ w, v });
	}

	//for (int i = 1; i < path.size(); ++i)
	//{
	//	for (int j = 0; j < path[i].size(); ++j)
	//	{
	//		cout << i << "번 정점에서 "
	//			<< path[i][j].second << "정점 까지의 가중치는 "
	//			<< path[i][j].first << "입니다. " << endl;
	//	}
	//}
	// 다익스트라 가자.
	vector<int> dist(vertex + 1, 987654321);
	dist[0] = 0;
	// 시작점은 정점의 개수 v보다는 작음.

	//vector<bool> visited(vertex + 1, false);

	// 가중치와 향하는 타겟팅 정점을 집어넣자.
	priority_queue<pair< int, int>> pq;
	pq.push({ 0, start });
	dist[start] = 0;

	//visited[start] = true;
	while (!pq.empty())
	{
		pair<int,int> target = pq.top();
		pq.pop();
		int cost = -target.first; // 비용
		int vv = target.second; // 타겟 정점.

		for (int i = 0; i < path[vv].size(); ++i)
		{
			int nextCost = path[vv][i].first;
			int nextNode = path[vv][i].second;

			if (nextCost + cost < dist[nextNode])
			{
				dist[nextNode] = nextCost + cost;
				pq.push({ -nextCost, nextNode });
			}
		}
	}

	for (int i = 1; i <= vertex; ++i)
	{
		if (dist[i] == 987654321)
		{
			//cout << "INF" << "\n";
			printf("INF\n");
		}
		else
		{
			//cout << dist[i] << "\n";
			printf("%d\n", dist[i]);
		}
	}

	return 0;
}

memset vs fill

https://velog.io/@kwt0124/memset-vs-fill-%EC%B0%A8%EC%9D%B4%EC%A0%90

🤔주의할 점.

• 여러개의 컨테이너를 우선순위 큐에 넣을때...
  

  -> 반드시, 1번째에 일반형, 2번째에서는 벡터형 , 3번째에는 내가
  반드시 비교 구조체를 전달해주자. : 정렬 부분에서 혼동하지 않기 위해

cout 사용하지 말자.

인자로 벡터 넘기지 말고, 전역 배열을 사용하자.

접근 법

• 최단 경로를 갱신할 수 있는 dist 배열 테이블이 필요함.
  dist 테이블은 경유해서 들어오는 dist와 비교를 함.
  -> 경유 dist가 더 크다면, 탐색 무시해버림.
  -> 불변수가 필요 없음!

• 시작의 dist는 자기자신으로 들어오는 값이므로 0으로 초기화를 함.

다익스트라 문제

1. dist 테이블에서 거리와 vs 우회회서 들어오는 값 + newDist 를 비교하게 되므로 , 방문 불변수 필요가 없음.

• 4번 노드를 기준으로해서 확인함.
  

• 2번 노드를 기준으로 해서 확인함.
  이때 2번에서 4번으로 향하게 되면, dist는 4 이지만,
  // 시작점인 1번에서 4번으로 가는 dist:1 이므로 무시됨.
  이를 처리한 부분이 밑의 코드임
  

if(dist[탐색중인 노드번호] < 탐색 예정인 dist)
continue;
이 부분 반드시 해야 함.

2. memset 보다는 fill 함수를 사용하자.

   fill(v.begin(), v.end() , 최대값)

3. 우선순위큐의 비교 연산자 공부하기 ,

• greater 일때와 less일때의 차이점.

배열을 인자로 전달하는 것은 포인터로 전달해야 함.

코드

#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <memory.h>
int dist[20001];
const int INF = 987654321;


struct compare
{
public:
	bool operator()(pair<int, int> a, pair<int, int>b)
	{
		return a.first > b.first;
	}

};
vector<pair<int, int>>node[20001];

void daikstra(vector<pair<int, int>>*node, int startNode)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>
		, compare>pq;
	// 자기 자신으로 까지의 비용은 0임.
	dist[startNode] = 0;
	pq.push(make_pair(0, startNode));

	while (!pq.empty())
	{
		int curNode = pq.top().second;
		int curDist = pq.top().first;

		pq.pop();

		if (dist[curNode] < curDist)
			continue;

		for (int i = 0; i < node[curNode].size(); ++i)
		{
			int nextNode = node[curNode][i].first;
			int tempDist = node[curNode][i].second;

			if (dist[nextNode] > tempDist + curDist)
			{
				dist[nextNode] = tempDist + curDist;
				pq.push(make_pair(dist[nextNode], nextNode));
			}
		}
	}
}


int main()
{
	int v, e;
	cin >> v >> e;

	int startNode;
	cin >> startNode;

	//v[1] 번 노드와 연결된 노드의 번호를 푸쉬백으로 저장하자.
	// 
	vector<pair<int, int>>node[20001];

	// 간선의 개수 
	for (int i = 0; i < e; ++i)
	{
		int a, b, c;
		cin >> a >> b >> c;

		node[a].push_back(make_pair(b, c));
	}

	fill(dist, dist + 20001, INF);

	daikstra(node, startNode);

	for (int i = 1; i <= v; ++i)
	{
		if (dist[i] == INF)
		{
			puts("INF");
		}
		else
		{
			printf("%d\n", dist[i]);
		}
	}
}