백준 1753번 : 최단 경로

문제 접근

---

알고리즘 문제해결 전략 책에서 다익스트라 알고리즘을 공부하고 이 문제를 풀었다. 처음에 priority_queue 우선 순위를 잘못 고려하고, INF 값을 너무 작게 넣어주는 실수를 해서 고쳤는데 틀렸다고 계속 틀렸다고 나와서 하루 종일 고민했다.

 

어제 연등 시간 끝나서 일단 생활관으로 돌아가 잤는데 꿈에서 여러가지 시도를 하다가 이 문제 AC 를 받았다. 난 '어, 맞았네?' 라고 생각하고 있는데 꿈에서 깰 것 같아서 '빨리 코드를 확인해야 돼!' 라고 생각하다가 깼다 ㅋㅋㅋ

 

뭔 꿈이지 싶어서 아침에 사지방 와서 확인해봤는데 배열 크기 잘못 지정해서 틀린 거였다 ㅋㅋㅋ. 진짜... 진짜 너무 즐겁다~ 정점이 20000 개고 1부터 시작하면 20001 으로 잡아줘야지 ㅎㅎㅎ vector 라고 헷갈리면 어떡하니 ㅎㅎㅎ

 

주의할 점!

1. priority_queue 우선 순위 확인할 것!

2. 배열 크기 확인할 것!

3. 멘탈 잡고, 안 되는 이유 계속 생각해볼 것!

 

 

문제 코드

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// 변수를 적게 사용하는 것보다 가독성을 중시해서 구현해봤다.
int V, E, source, u, v, w;
int here, closest, there, nextDist;

vector<pair<int,int>> graph[20001];
vector<int> dist(20001,3000001);
priority_queue<pair<int,int>> q;

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>V>>E;
	cin>>source;
	
	while(E--)
	{
		cin>>u>>v>>w;
		graph[u].push_back(make_pair(v,w));
	}
	
	dist[source] = 0;
	// priority_queue 에서 pair 의 첫번째 원소를 기준으로 정렬하기에 첫번째 원소에 weight 가 들어가야 한다.
    q.push(make_pair(0,source));
	
	while(!q.empty())
	{
    	// 기본적인 priority_queue 는 내림차순으로 정렬하기에 - 를 붙여 오름차순으로 바꿨다.
		here = q.top().second;
		closest = -q.top().first;
		q.pop();
		
		if(closest > dist[here])
			continue;
		
		for(int i=0; i<graph[here].size(); ++i)
		{
			there = graph[here][i].first;
			nextDist = closest + graph[here][i].second;
			
			if(nextDist < dist[there])
			{
				dist[there] = nextDist;
				q.push(make_pair(-nextDist, there));
			}
		}
	}
	
	for(int i=1; i<=V; ++i)
	{
		if(dist[i]==3000001)
			cout<<"INF\n";
		else
			cout<<dist[i]<<'\n';
	}
}

 

결과 ( 바보같은 전투의 흔적 )

---