백준 1446 - 지름길(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1446

1446번: 지름길

다익스트라를 이용한 문제입니다.

현재 위치에서 지름길을 통해 이동하거나, 다음 위치로 이동하는 과정을 거쳐, 원하는 목적지까지 최소 이동거리로 이동하는 문제입니다.

먼저 Distancs배열을 만들어줍니다. 해당 배열을 N번째 위치를 얼마의 최솟값으로 이동할 수 있는지를 저장하는 배열입니다.
-> 해당 배열은 처음에 무한히 큰 값으로 초기화를 해줘야합니다. 초기화를 통해 큰 값을 저장해줘야지, 해당 배열의 값을 바꾸면서 탐색이 가능합니다.

시작하는 위치에서 탐색을 시작할 때 갈 수 있는 방법은 2가지입니다.
1. 현재 위치에서 지름길이 있을 경우, 지름길을 통해 이동한다.
2. +1 번째 위치로 이동한다.(지름길이 없을 경우 해당 방법만 이용 가능합니다.)

2가지 방법 모두 값이 1이므로, 이동한 좌표의 값은 Distance[현재위치] + 1의 값을 가질 수 있게 됩니다.
이 값을 현재 이동할 정점의 값과 비교한 뒤, 최솟값을 선택하면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#define INF 2100000000
#define F first
#define S second

using namespace std;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; //우선순위 큐, first의 값을 기준으로 오름차순으로 정렬
int N, M;
int Distance[10001]; // 1~M까지 최단 거리를 저장
bool check[10001]; // 이전에 방문했는지 여부를 확인
vector<pair<int, int>> connect[10001]; //X번째 vector에 (지름길 도착 번호, 지름길 길이)를 저장한다

void reset_distacne(){
	for(int i = 0; i <= M; i++) Distance[i] = INF; // 처음에는 INF의 값으로초기화를 시켜, 항상 크게 만들어준다.
}

void solve(){
	reset_distacne();
	memset(check, false, sizeof(check));
	Distance[0] = 0;
	q.push({Distance[0], 0}); // 거리값을 먼저 넣어야지 오름차순으로 정렬이된다.
	while(!q.empty()){
		int x = q.top().S;
		int cost = q.top().F;
		q.pop();
		check[x] = true;
		if(connect[x].size() > 0){
			for(int i = 0; i < connect[x].size(); i++){
				int xx = connect[x][i].F;
				int Cost = connect[x][i].S;
				if(!check[xx] && Distance[xx] > Distance[x] + Cost){ //도착할 곳이 현재 정점에서 갈 수 있는 방법보다 거리가 큰 경우
					Distance[xx] = Distance[x] + Cost;
					q.push({Distance[xx], xx});
				}
			}
		}
		int xx = x + 1; // x에서 1km는 갈 수 있는 곳이니 해당 정점도 확인해준다
		if(!check[xx] && Distance[xx] > Distance[x] + 1){ 
			Distance[xx] = Distance[x] + 1;
			q.push({Distance[xx], xx});
		}
	}
	cout << Distance[M];
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= N; i++){
		int x, y, cost;
		cin >> x >> y >> cost;
		connect[x].push_back({y, cost});
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.