[ 백준 1238 ] 파티 (C++)

 

 

 

1238번: 파티

문제!

---

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

 

---

요약하면 각각의 마을에 학생들이 사는데 X마을에서 파티를 하기 위해 모두 이동할 예정이다!

  >> 이때 오고가는 이동 시간이 가장 긴 학생의 소요시간을 출력하는 문제입니다. 

 

 

 

처음 보았을땐 단순 탐색인줄알고 풀어낼려 했는데

 

X마을이라는 공통 목적지가 있기에 다익스트라 알고리즘을 사용하는것이 좋을 것 같다고 생각해보았습니다. 

1. 각 마을 간의 길 정보를 입력받고

2.  각 마을로부터 X까지의 최단거리를 구해줍니다.

3. 이제 돌아오는길 X로부터의 각 마을 최단거리를 구해줍니다.

4. 최장 거리 출력!

 

 

 

 

코드!

---

 

그렇게 구현한 알고리즘은 실패.. 방문처리를 어떻게 해야할지 생각하다 꼬여버렸네요

 

완전히 잘못 생각한것 같네요

do  {
		cout << "---시작" << endl;
		int Tempdistance=987654321;

		int NextLocationind = 0;
		int distance = 0;
		

		for (int i = 0; i < Loads[NowLocation].size(); i++) { // 현재위치에서 갈수 있는곳 넣어주기
			if (visited[Loads[NowLocation][i].end] == 0) {//방문안한것만
				if (distanceList[Loads[NowLocation][i].end] > Loads[NowLocation][i].dist + distanceList[NowLocation]) { // 거리비교 후 최신화
					distanceList[Loads[NowLocation][i].end] = Loads[NowLocation][i].dist + distanceList[NowLocation];
				}
			}
		}


		for (int i = 1; i <= N; i++) { // 제일 가중치가 작은곳 선택하기 
			if (Tempdistance > distanceList[i] && visited[i] == 0) {
				NextLocationind = i;
			}
		}
		
		NowLocation = Loads[NowLocation][NextLocationind].end;
		//distanceList[NowLocation] = Tempdistance;
		visited[NowLocation] = 1; // 방문처리		


	} while (TempList.size() != 0);

 

 

그렇게 찾아보다 우선순위를 이용한 다익스트라 알고리즘에서는

방문여부를 체크해주지 않아도 된다는 점을 알게되었습니다. 

 

 

다시시작!

 

먼저 선언부

// N명의 학생이 N번 마을에 모여 파티를 벌임 >> 길이 있음 

int N, M, X; // 학생 , 마을 사이의 도로갯수 , 모이는 마을 번호

// 각 도록의 시작 / 끝 / 시간  >> 단방향


struct Load
{
	int end;
	int dist;
};

vector<Load>Loads[2][1001];
vector<int>distanceList[2]; // 파티 마을에서 각각의 마을까지
vector<int>visited(1001, 0); // 파티 마을에서 각각의 마을까지
vector<Load>TempList;

int answer = 0;

 

 

 

입력을 받으며 거리벡터를 다시 선언해줍시다.

int main() {

	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) { // 길 받기
		int start, end, dist;
		cin >> start >> end >> dist;

		Load temp;
		temp.end = end;
		temp.dist = dist;
		Loads[0][start].push_back(temp);  // 길 저장

		temp.end = start;
		Loads[1][end].push_back(temp);
        
		distanceList[0].resize(N + 1, 987654321);
		distanceList[1].resize(N + 1, 987654321);
	}

 

 

제일 중요한 다익스트라 부분

void Dijstra(int k) {
	distanceList[k][X] = 0;

	priority_queue<pair<int, int>> que;

	que.push({ 0, X });


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


		if (min_cost > distanceList[k][now]) {
			continue;
		}

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

			int next = Loads[k][now][i].end;
			int next_cost = min_cost + Loads[k][now][i].dist;

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

 

제가 구현 하려던코드는 현재 부분에서 연결된 부분들을 계속 담아가며 방문한 노드는 버리는 코드를 구상했는데

 

우선순위를 이용하면 따로 방문 처리를 하지 않아도 최소가 아니면 자동으로 걸러지기에 생각할게 많이 줄어드네요...

 

 

<다익스트라>

현재 이동할 수 있는 노드들중 이동 거리가 가장 짧은 위치부터 탐색하여

한 목적지에서 모든 노드로의 최단거리를 구하는 알고리즘입니다.  

 

 

여기까지하면 

1. 각 마을 간의 길 정보를 입력받고

2.  각 마을로부터 X까지의 최단거리를 구해줍니다.

까지 해결!

 

3번은  for문을 통해 모든 노드에서 다익스트라 알고리즘을 실행 시킬려고 했으나

생각보다 간단한 방법이 있었습니다.....

 

경로를 역으로 설정하여 다시 각 지역에서 x지역으로의 최단거리를 구해주는 방법;;;;

 

 

 

그래서 상단에서 

 

이런식으로 Loads를 1, 2 로 나누어 받아 주었습니다. 

Load temp;
		temp.end = end;
		temp.dist = dist;
		Loads[0][start].push_back(temp);  // 길 저장

		temp.end = start;
		Loads[1][end].push_back(temp);

 

 

그러면 아래처럼 끝....

	Dijstra(1);
	Dijstra(0);

	for (int i = 1; i <= N; i++) {
		answer = max(answer, distanceList[0][i] + distanceList[1][i]);
	}



	cout << answer << endl;

 

 

다익스트라에 대해 다시배운것 같네요..

1. 우선순위 사용하자..

2. 방향을 역으로 돌리는 부분도 생각해보자

 

 

 

ALL

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <deque>
#include <queue>
#include <deque>
using namespace std;



// N명의 학생이 N번 마을에 모여 파티를 벌임 >> 길이 있음 

int N, M, X; // 학생 , 마을 사이의 도로갯수 , 모이는 마을 번호

// 각 도록의 시작 / 끝 / 시간  >> 단방향


struct Load
{
	int end;
	int dist;
};

vector<Load>Loads[2][1001];
vector<int>distanceList[2]; // 파티 마을에서 각각의 마을까지
vector<int>visited(1001, 0); // 파티 마을에서 각각의 마을까지
vector<Load>TempList;

int answer = 0;


void Dijstra(int k) {
	distanceList[k][X] = 0;

	priority_queue<pair<int, int>> que;

	que.push({ 0, X });


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


		if (min_cost > distanceList[k][now]) {
			continue;
		}

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

			int next = Loads[k][now][i].end;
			int next_cost = min_cost + Loads[k][now][i].dist;

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





int main() {

	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) { // 길 받기
		int start, end, dist;
		cin >> start >> end >> dist;

		Load temp;
		temp.end = end;
		temp.dist = dist;

		Loads[0][start].push_back(temp);  // 길 저장

		temp.end = start;

		Loads[1][end].push_back(temp);
		distanceList[0].resize(N + 1, 987654321);
		distanceList[1].resize(N + 1, 987654321);
	}


	Dijstra(1);
	Dijstra(0);

	for (int i = 1; i <= N; i++) {
		answer = max(answer, distanceList[0][i] + distanceList[1][i]);
	}



	cout << answer << endl;

	/// X 로부터 각 마을 까지의 거리!

	return 0;
}

 

 

 

 

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