급하게임개발

https://www.acmicpc.net/problem/17835

이 문제는 처음에는 역 다익스트라를 면접장에서 구해서 최소 면접점을 구해서 했는데 시간 복잡도가 나왔다

이문제를 풀면서 처음안건데 멀티소스다익스트라라는 것이 있었다 이 알고리즘은 다익스트라의 시작점에 여러개를 넣고 시작하는데 이때 distacneV 벡터에는 각 시작점들에서 부터 그지점까지 가는곳의 최솟 값이 저장된다 즉 어디서 왔는지에 대해서는 모르지만 여러시작점들중 나까지 오는데의 최소 거리는 알수 있다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 50000000001

int n, m, k;
vector<pair<int, long long>> edgeList[100001];  // 1번부터 n번까지 사용 (문제 constraints에 따라)
vector<long long> dist;  // 각 도시까지의 최단 거리

// 멀티 소스 다익스트라: 여러 시작점을 동시에 처리
void multiSourceDijkstra(const vector<int>& startNodes) {
    dist.assign(n + 1, INF);
    // (거리, 노드)를 저장하는 최소 힙
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    // 모든 면접 장소를 초기 노드로 넣고 거리를 0으로 설정
    for (int node : startNodes) {
        dist[node] = 0;
        pq.push({ 0, node });
    }

    while (!pq.empty()) {
        int cur = pq.top().second;
        long long curCost = pq.top().first;
        pq.pop();

        if (curCost > dist[cur])
            continue;

        // 인접 노드 업데이트
        for (auto& edge : edgeList[cur]) {
            int next = edge.first;
            long long nextCost = edge.second;
            if (dist[next] > curCost + nextCost) {
                dist[next] = curCost + nextCost;
                pq.push({ dist[next], next });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;

    // 도로 정보를 입력받으며, 문제의 조건에 맞게 간선의 방향을 반대로 저장합니다.
    int from, to;
    long long cost;
    for (int i = 0; i < m; i++) {
        cin >> from >> to >> cost;
        // 인터뷰 장소로의 최단 경로를 구하기 위해 간선의 방향을 반대로 저장
        edgeList[to].push_back({ from, cost });
    }

    vector<int> interviewLocations(k);
    for (int i = 0; i < k; i++) {
        cin >> interviewLocations[i];
    }

    // 멀티 소스 다익스트라 실행
    multiSourceDijkstra(interviewLocations);

    // 각 도시에서 면접 장소까지의 최단 거리가 최대인 도시를 찾습니다.
    int answerCity = 0;
    long long maxDistance = -1;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > maxDistance) {
            maxDistance = dist[i];
            answerCity = i;
        }
    }

    cout << answerCity << "\n" << maxDistance << "\n";

    return 0;
}

https://www.acmicpc.net/problem/1719

이 문제는 m 으로 입력받아야하는데 n으로 입력받아서 로직으로는 맞는데 계속 틀린값이 나와서 멘탈나갈뻔했다 일단 이문제는 그냥 이제 i->j 로갈때의 첫번째 노드를 저장해놓는 배열을 따로 만들어 놓고 해당 배열을 통해 지속적으로 업데이트 해주면 되는 문제였다

#include <iostream>
using namespace std;
#define INF 200000000

// 여기는 경로 코스트 저장
int arr[201][201];
// 여기는 j로 가는 가장 먼저 방문해야 할 곳 저장
int arr2[201][201];

int n, m;

int main() {
    cin >> n >> m;
    int t1, t2, t3;

    // 거리 배열 초기화
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                arr[i][j] = 0;
            }
            else {
                arr[i][j] = INF;
                arr2[i][j] = j;  // 초기 방문 노드를 j로 설정
            }
        }
    }

    // 간선 정보 입력
    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2 >> t3;
        arr[t1][t2] = t3;
        arr[t2][t1] = t3;
        arr2[t1][t2] = t2;
        arr2[t2][t1] = t1;
    }

    // 플로이드-워셜 알고리즘
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (arr[i][j] > arr[i][k] + arr[k][j]) {
                    arr[i][j] = arr[i][k] + arr[k][j];
                    arr2[i][j] = arr2[i][k]; // i -> j로 가는 첫 방문 노드 업데이트
                }
            }
        }
    }

    // 결과 출력
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) cout << "- ";
            else cout << arr2[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

https://www.acmicpc.net/problem/14284

이 문제는 다익스트라 알고리즘을 사용해서 풀 수 있다 현재 이블로그에 있는 다익스트라 알고리즘에 관한 문제는 비슷한 양상을 보인다

void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ startNode,toCost });

	while (!djikstra_pq.empty()) {
		int toVertex = djikstra_pq.top().first;
		int toCost = djikstra_pq.top().second;

		djikstra_pq.pop();

		int distanceToNextVertex = distanceV[toVertex];
		if (distanceToNextVertex < toCost) {
			continue;
		}
		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			// 다음 인덱스로 가는 cost
			int cost = edgeList[toVertex][i].second + toCost;
			// 나를 통해 갈 다음 IDX
			int nextIdx = edgeList[toVertex][i].first;
			if (cost < distanceV[nextIdx]) {
				distanceV[nextIdx] = cost;
				djikstra_pq.push({ nextIdx,cost });
			}
		}


	}
}

이 부분이 핵심 부분인데

1. 일단 start 즉 시작점으로 부터의 거리를 구할 것이기에 Start -> Start의 toCost를 0 start->start의 다음인덱스 start를 우선순위 큐에 넣는다 (우선순위 큐는 값이 작은게 root 에 있다)

2.그리고 우선순위 큐가 빌때 까지 
현재 우선순위 큐에 들어가 있는 버텍스와 경로들을 뽑아서 해당 경로들에  영향을 받는 다른 vertex들의 cost값을 업데이트 해줘야 한다

3.일단 node1 -> node2 로 갈때의  현재 우선순위 큐에들어가 있는 가장 작은 애를 가져온다 그후 내가 node1을 통해서 가는 node2 까지의 거리와 이전부터 업데이트  해놓은 1부터 node2까지의 거리를 비교해서 작은 값일 때  node2를 통해서 가는 거리들의 값을 업데이트 해준다 그후 다음 업데이트를 할수도 있으니 해당 값들을 우선순위 큐에 넣어주고 반복한다

전체 코드는 아래와 같다

#include <iostream>
#include<queue>
using namespace std;
int n, m;

#define INF 1e9+7
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> djikstra_pq;
vector<pair<int, int>> edgeList[5001];
vector<int> distanceV(5001);
void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ startNode,toCost });

	while (!djikstra_pq.empty()) {
		int toVertex = djikstra_pq.top().first;
		int toCost = djikstra_pq.top().second;

		djikstra_pq.pop();

		int distanceToNextVertex = distanceV[toVertex];
		if (distanceToNextVertex < toCost) {
			continue;
		}
		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			// 다음 인덱스로 가는 cost
			int cost = edgeList[toVertex][i].second + toCost;
			// 나를 통해 갈 다음 IDX
			int nextIdx = edgeList[toVertex][i].first;
			if (cost < distanceV[nextIdx]) {
				distanceV[nextIdx] = cost;
				djikstra_pq.push({ nextIdx,cost });
			}
		}


	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int temp1, temp2, temp3;
		cin >> temp1 >> temp2 >> temp3;

		edgeList[temp1].push_back({ temp2,temp3 });
		edgeList[temp2].push_back({ temp1,temp3 });

	}
	int start, end;
	cin >> start >> end;

	distanceV.assign(n + 1, INF);
	djikstraSolution(start);

	cout << distanceV[end];
}