[백준] 13168 내일로 여행

백준 13168 내일로 여행 문제 풀이입니다.

내일로 여행

이 문제는 노드 갯수가 적기 때문에 시간복잡도가 O(n^3)인 플로이드 와샬 방법으로 풀 수 있습니다.

다만 플로이드 와샬 예제들처럼 노드가 0,1,2같은 숫자로 되있는 것이 아니기 때문에 데이터 전처리가 필요한 문제였습니다.

우선 입력받은 도시를 순서대로 map에 저장하였습니다. 즉 예제들과 같이 1번 도시 2번 도시처럼 각 도시 이름이 인덱스를 가지게 되는 것입니다.

그 다음 내일로를 이용할 시 최소 비용과 전부다 이용시 최소 비용 총 두가지 배열을 사용하여 로직을 세웠습니다.

이후 나머지 방법은 플로이드 와샬 기본 방법과 똑같습니다.

소스코드는 다음과 같습니다.

Source Code:

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

#define MAX 101
#define INF 987654321

int N, R, M, K;

map<string,int> city; // 도시 인덱스 저장 0~N-1 
vector<string> travel;

int traffic_dist[MAX][MAX];
int naeilo_dist[MAX][MAX];


int main() {

	cin >> N >> R;

	for (int i = 0; i < N; i++) {
		string tmp;
		cin >> tmp;
		city[tmp] = i;
	}

	cin >> M;

	for (int i = 0; i < M; i++) {
		string tmp;
		cin >> tmp;
		travel.push_back(tmp);
	}

	cin >> K;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i != j) {
				traffic_dist[i][j] = INF;
				naeilo_dist[i][j] = INF;
			}
		}
	}

	for (int i = 0; i < K; i++) {
		string traffic, start, destination;
		int cost;
		cin >> traffic >> start >> destination >> cost;

		int start_idx = city[start];
		int des_idx = city[destination];

		traffic_dist[start_idx][des_idx] = min(traffic_dist[start_idx][des_idx], cost);
		traffic_dist[des_idx][start_idx] = min(traffic_dist[des_idx][start_idx], cost);
		
		if (traffic == "S-Train" || traffic == "V-Train" ) {
			cost /= 2;
		}
		else if(traffic == "ITX-Saemaeul" || traffic == "ITX-Cheongchun" || traffic == "Mugunghwa") {
			cost = 0;
		}

		naeilo_dist[start_idx][des_idx] = min(naeilo_dist[start_idx][des_idx], cost);
		naeilo_dist[des_idx][start_idx] = min(naeilo_dist[des_idx][start_idx], cost);
	}

	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				traffic_dist[i][j] = min(traffic_dist[i][j], traffic_dist[i][k] + traffic_dist[k][j]);
				naeilo_dist[i][j] = min(naeilo_dist[i][j], naeilo_dist[i][k] + naeilo_dist[k][j]);
			}
		}
	}

	long long General = 0, Discount = 0;

	for (int i = 0; i < M-1; i++) {
		string start_city = travel[i];
		string des_city = travel[i + 1];
		int start = city[start_city];
		int des = city[des_city];

		General += traffic_dist[start][des];
		Discount += naeilo_dist[start][des];
	}

	if (General <= Discount + R) cout << "No";
	else cout << "Yes";

	return 0;
}

궁금하신 점은 댓글 남겨 주세요!!

Summary

• 너무 오랜만에 푸는 알고리즘 문제라서 너무 재밌었습니다 ㅠㅠ
• 그래프는 항상 풀어도 부족하기 때문에 더더욱 열심히 해야겠다고 생각했습니다.
• 3달동안 코딩 쉬었더니 코테 다 탈락하고 .. 싱숭생숭할때 풀어서 더욱 아쉬움이 남는…