[ 백준 1504 ] 특정한 최단경로 (C++)

 

 

1504번: 특정한 최단 경로

문제!

---

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

 

---

요약하면 1번 정점에서  N번 정점으로 이동할때 추가로 두 정점을 거쳐 이동하는

최단경로의 길이를 출력하는 문제입니다. 

 

 

 

최단경로? >> dfs?  

바로 깊이 탐색 코드에 대해 작성했습니다...

하지만 실패.. 시간초과 나네요

 

 

시간초과 코드..

단순 dfs로는 시간초과 나네요...

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

using namespace std;

int N, E;

/// a b c >> a에서 b 까지 거리 c

int target1, target2; // 꼭 거쳐야되는           1번 정점  >> 타겟1 >> 타겟2 >> N번 정점  //   1번 정점  >> 타겟2 >> 타겟1 >> N번 정점

vector<vector<pair<int,int>>>Map;
vector<int>visited;

int answer = 987654321;
int check = 0;



void dfs(int start,int end, int count) {
	if (start == end && check==2) {
		answer = min(answer, count);
		return;
	}

	if (answer <= count) {
		return;
	}

	for (int i = 0; i < Map[start].size(); i++) {
		int tempInd = Map[start][i].first; //
		int tempDist = Map[start][i].second; //

		if (visited[tempInd] == 0) {
			if (target1 == tempInd || target2 == tempInd) {
				check += 1;
			}
			visited[tempInd] = 1;
			dfs(tempInd, end, count + tempDist);
			visited[tempInd] = 0;

			if (target1 == tempInd || target2 == tempInd) {
				check -= 1;
			}

		}
	}

	return;
}



int main() {
	
	cin >> N >> E;
	Map.resize(N + 1); // 맵 길이
	visited.resize(N + 1, 0);

	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		Map[a].push_back(make_pair(b,c));
		Map[b].push_back(make_pair(a, c)); // 길 저장
	}

	cin >> target1 >> target2;



	dfs(1, N, 0);
	
	cout << answer << endl;
	
	


	return 0;
}

 

다시 한번 생각해보니 탐색이라고 해도 경로를 저장하는 게 아니면 다익스트라 알고리즘을 쓰는 게 맞는 거 같습니다..!

 

 

그래서 이번엔 다익스트라 알고리즘을 사용해 보았습니다. 

 

어떻게?

 

1번과 두 정점, N번 정점까지의 이동 순서는 아래와 같습니다.

 

1번 정점 >> 타겟1 >> 타깃 2 >> N번 정점 

1번 정점  >> 타겟2 >> 타깃 1 >> N번 정점

 

 

이렇게 2가지로 생각하여 풀어내면 될것 같습니다!

 

 

 

코드

---

 

먼저 몇가지 선언해 줍시다.

int N, E;

/// a b c >> a에서 b 까지 거리 c

int target1, target2; // 꼭 거쳐야되는           

vector<pair<int,int>>Map[801]; // 전체 맵 구조리스트

int distanceList[801]; // 거리 리스트
int answer = 987654321;

 

그리고 입력을 받아줍시다.

cin >> N >> E;
for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		Map[a].push_back(make_pair(b,c));
		Map[b].push_back(make_pair(a, c)); // 길 저장
	}

	cin >> target1 >> target2;

 

 

다음은 다익스트라 알고리즘!

 

이 코드에서는 다익스트라 알고리즘을 여러 번 돌릴 것이기에

void DistReset() {
	for (int i = 0; i <= N; i++) {
		distanceList[i] = 987654321;
	}
}

초기화 함수를 하나 만들어주고

 

 

 

다익스트라 함수를 구현해 줍시다.

void Dijstra(int k) {
	DistReset();

	distanceList[k] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
	que.push({ 0, k });


	while (!que.empty()) {
		int min_cost = que.top().first;
		int now = que.top().second;
		que.pop();

		for (int i = 0; i < Map[now].size(); i++) {

			int next = Map[now][i].first;
			int next_cost = min_cost + Map[now][i].second;

			if (next_cost < distanceList[next]) {  /// 단순 비교후 선택
				distanceList[next] = next_cost;
				que.push({next_cost,next});
			}
		}
	}
}

여기까지 했다면 끝!

 

 

이제 이동 순서에 따라 다익스트라 알고리즘을 실행해 주며 길이를 구해주어야 합니다.

 

 

여기서 다시 한번 문제가 발생했는데

 

아래처럼  두 가지 경로

1번 정점 >> 타깃 1 >> 타겟2 >> N번 정점

1번 정점  >> 타겟2 >> 타겟1 >> N번 정점

에 대해 way1, way2에 각각 저장해 두고 

	Dijstra(1);
	int Way1=0, Way2 = 0;

	Way1 += distanceList[target1];
	Way2 += distanceList[target2];

	Dijstra(target1);
	Way1 += distanceList[target2];
	Way2 += distanceList[N];

	Dijstra(target2);
	Way1 += distanceList[N];
	Way2 += distanceList[target1];

	answer = min(Way1, Way2);

	if (answer >= 987654321) {
		answer = -1;
	}

	cout << answer << endl;

마지막 부분에서 도착하지 못하였을 때를 따로 해결해 주었습니다...

 

혹시 눈치채셨나요?

int 형인 answer에 987654321이라는 최댓값이 2번 정도 더해지면 감당할 수 없어 터져 버립니다...

그래서 if문이 정상적으로 작동할 수 없었습니다....

 

 

 

그렇기에 int 형 대신 long long 형을 사용하여 해결해 줍시다!

Dijstra(1);
	long long Way1 = 0, Way2 = 0;

	Way1 += distanceList[target1];
	Way2 += distanceList[target2];

	Dijstra(target1);
	Way1 += distanceList[target2];
	Way2 += distanceList[N];

	Dijstra(target2);
	Way1 += distanceList[N];
	Way2 += distanceList[target1];

	answer = min(Way1, Way2);

	if (answer >= 987654321) {
		answer = -1;
	}

	cout << answer << endl;

 

 

여기까지가 끝!

 

이번 문제를 통해 다시 한번 배운 내용

1. 경로가 필요하지 않으면, 다익스트라를 사용하자

2. 그 변수에 대해 형의 범위를 넘어가는지도 생각해 보자

 

생각보다 헤매었네요..

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

using namespace std;

int N, E;

/// a b c >> a에서 b 까지 거리 c

int target1, target2; // 꼭 거쳐야되는           

vector<pair<int,int>>Map[801];

int distanceList[801];
long long answer = 987654321;



void DistReset() {
	for (int i = 0; i <= N; i++) {
		distanceList[i] = 987654321;
	}
}


void Dijstra(int k) {
	DistReset();

	distanceList[k] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
	que.push({ 0, k });


	while (!que.empty()) {
		int min_cost = que.top().first;
		int now = que.top().second;
		que.pop();

		for (int i = 0; i < Map[now].size(); i++) {

			int next = Map[now][i].first;
			int next_cost = min_cost + Map[now][i].second;

			if (next_cost < distanceList[next]) {  /// 단순 비교후 선택
				distanceList[next] = next_cost;
				que.push({next_cost,next});
			}
		}
	}
}



int main() {
	
	cin >> N >> E;


	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		Map[a].push_back(make_pair(b,c));
		Map[b].push_back(make_pair(a, c)); // 길 저장
	}

	cin >> target1 >> target2;


	//1번 정점 >> 타겟1 >> 타겟2 >> N번 정점  |||   1번 정점  >> 타겟2 >> 타겟1 >> N번 정점

	Dijstra(1);
	long long Way1 = 0, Way2 = 0;

	Way1 += distanceList[target1];
	Way2 += distanceList[target2];

	Dijstra(target1);
	Way1 += distanceList[target2];
	Way2 += distanceList[N];

	Dijstra(target2);
	Way1 += distanceList[N];
	Way2 += distanceList[target1];




	answer = min(Way1, Way2);




	if (answer >= 987654321) {
		answer = -1;
	}

	cout << answer << endl;



	return 0;
}

 

 

 

 

틀린 점이 있다면 댓 달아주세요!