[백준] 1446번 - 지름길 (C++)

1446번: 지름길

 

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

 

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

 

 

출력

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

 

 

풀이과정

문제부터 이해가 잘 가지 않아 예제 1번부터 해석을 해보았습니다.

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

위와 같은 형식으로 입력값이 주어질 때 0부터 150까지 가는 최소거리를 구하는 문제였습니다.

0 ~ 50 까지는 10이라는 지름길을 사용하는게 효율적이니 사용을 하고 50 ~ 100까지도 10이라는 지름길을 사용합니다.

100 ~ 151은 151까지 가버린 상황에서는 다시 되돌아갈 수 없기 때문에 사용이 불가능하고

110 ~ 140은 거리가 90이라 그냥 가는것보다 거리가 더 많이 들어 패스를 하면 남아있는 지름길이 없어서 100 ~ 150은 그냥 길로 가면

10 + 10 + 50 으로 70이라는 값이 나오기 되는 문제였습니다.

 

해당문제에서 요구하는 알고리즘이 데이크스트라라는 알고리즘을 요구하는 문제라서 해당 개념을 잡는 게 상당히 어려웠던 거 같습니다.

문제를 해결했던 과정은 다음과 같이 풀었었습니다.

최종적으로 문제에서 알아내야하는 D(최종도착지점)까지 가는 가장 작은 값을 찾아야 하니  dp와 같이 이전에 지나온 길들을 바탕으로

새로운 길들을 새롭게 갱신해나가는 방식을 사용하였습니다.

지름길의 도착지점을 기준으로 시작지점을 바라보면 시작지점까지 걸린 거리 + 지름길의 거리가 지름길 도착지점까지 중 가장 빠르게 도착할 수 있는 거리라는 형식으로 점화식을 세워 문제의 접근을 해보았습니다.

 

code

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

const int INF = 10001;
int m[INF];
std::vector <std::pair<int, int> > vec[INF];

void	dijkstra(int d)
{
	m[0] = 0;
	for (int i = 1; i <= d; i++) {
		m[i] = m[i - 1] + 1;
		for (int j = 0; j < (int)vec[i].size(); j++) {
			m[i] = std::min(m[i], m[vec[i][j].first] + vec[i][j].second);
		}
	}
}

int		main(void)
{
	int n, d, u, v, num;

	std::cin >> n >> d;
	std::fill_n(m, INF, INF);
	for (int i = 0; i < n; i++) {
		std::cin >> u >> v >> num;
		if (d < v || v - u < num) continue;
		vec[v].push_back(std::make_pair(u, num));
	}
	dijkstra(d);
	std::cout << m[d];

	return (0);
}

 

후기

데이크스트라는 뭔가 dp랑 유사하다라는 느낌을 많이 받았던 거 같다.

처음 접해봐서 그런지 어떻게 접근을 해야할지 너무 어렵다는 느낌을 받았었다.