급하게임개발

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/9370

이 문제는 처음에 플로이드로 풀다가 시간초과  나서  djikstra로 변경하였다 이문제는 그냥 다익스트라를 세번 돌리면 되는데

       int route1 = dist_s[g] + g_h_cost + dist_h[dest]; // s -> g -> h -> dest
       int route2 = dist_s[h] + g_h_cost + dist_g[dest]; // s -> h -> g -> dest

이렇게 실제 거리와 g_h를 지나는 거리와 똑같다면 g -> h를 지나간다고 판별 할 수 있으니
이를 이용해서 목적지까지의 거리가 같으면 priority_queue에 넣은 후 차례로  pop하면 되는 문제였다

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

using namespace std;

#define INF 1000000001

int t, n, m, d;
int s, g, h;
vector<pair<int, int>> edgeList[2001];
vector<int> distance_v;

void dijkstra(int start, vector<int>& dist) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist.assign(n + 1, INF);
    dist[start] = 0;
    pq.push({ 0, start });

    while (!pq.empty()) {
        int cur_cost = pq.top().first;
        int cur_vertex = pq.top().second;
        pq.pop();

        if (cur_cost > dist[cur_vertex])
            continue;

        for (auto next : edgeList[cur_vertex]) {
            int next_vertex = next.first;
            int next_cost = next.second;

            if (dist[next_vertex] > cur_cost + next_cost) {
                dist[next_vertex] = cur_cost + next_cost;
                pq.push({ dist[next_vertex], next_vertex });
            }
        }
    }
}

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

    cin >> t;
    while (t--) {
        cin >> n >> m >> d;
        cin >> s >> g >> h;

        for (int i = 0; i <= n; i++) {
            edgeList[i].clear();
        }

        int g_h_cost = 0;
        for (int i = 0; i < m; i++) {
            int from, to, cost;
            cin >> from >> to >> cost;
            edgeList[from].push_back({ to, cost });
            edgeList[to].push_back({ from, cost });

            if ((from == g && to == h) || (from == h && to == g)) {
                g_h_cost = cost; // g-h 간선의 비용 저장
            }
        }

        // 다익스트라 실행
        vector<int> dist_s(n + 1), dist_g(n + 1), dist_h(n + 1);
        dijkstra(s, dist_s);
        dijkstra(g, dist_g);
        dijkstra(h, dist_h);

        priority_queue<int, vector<int>, greater<int>> destination_pq;
        for (int i = 0; i < d; i++) {
            int dest;
            cin >> dest;

            int route1 = dist_s[g] + g_h_cost + dist_h[dest]; // s -> g -> h -> dest
            int route2 = dist_s[h] + g_h_cost + dist_g[dest]; // s -> h -> g -> dest

            if (dist_s[dest] == route1 || dist_s[dest] == route2) {
                destination_pq.push(dest);
            }
        }

        // 결과 출력
        while (!destination_pq.empty()) {
            cout << destination_pq.top() << " ";
            destination_pq.pop();
        }
        cout << endl;
    }
}

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/17396

이 문제는 다 풀어놓고 하나를 실수 해서 조금 헤맸었다
이 문제는 일반적인 다익스트라 문제이다 이에 소스코드는 이렇게 되고 25% 에서 이슈가 있었다

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> djikstra_pq;
vector<pair<int, int>> edgeList[100000];
vector<int> distance_v;
int testCase;
int n, d, c;
#define INF 1000000001
void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ toCost,startNode });
	while (!djikstra_pq.empty())
	{
		int vertex = djikstra_pq.top().second;
		int toCost = djikstra_pq.top().first;
		djikstra_pq.pop();
		if (toCost > distance_v[vertex])
			continue;

		for (int i = 0; i < edgeList[vertex].size(); i++) {
			int nextVertex = edgeList[vertex][i].first;
			int nextCost = edgeList[vertex][i].second;
			if (distance_v[nextVertex] > nextCost + toCost) {
				distance_v[nextVertex] = nextCost + toCost;
				djikstra_pq.push({ nextCost + toCost,nextVertex });
			}
		}
	}
}
int main() {
	cin >> testCase;
	for (int i = 0; i < testCase; i++) {
		cin >> n >> d >> c;
		for (int i = 0; i < d; i++) {
			int from, to, cost;
			cin >> from >> to >> cost;
			edgeList[to].push_back({ from,cost });
		}
		distance_v.assign(n + 1, INF);
		int cpuCnt, lastSecond;
		djikstraSolution(c);
		lastSecond = 0;
		cpuCnt = 0;
		distance_v[c] = 0;
		for (int i = 1; i <= n; i++) {
			if (distance_v[i] != INF) {
				cpuCnt++;
				if (distance_v[i] > lastSecond) {
					lastSecond = distance_v[i];
				}
			}
			edgeList[i].clear();
		}
		cout << cpuCnt << " " << lastSecond << endl;
	}
}

이런식으로 되는데 내가 처음에 distanceVector를 초기화 해줄 때 나에서부터 나까지의  거리는 0이라고 설정을 안해놓았었다 그 후 무조건 감염 PC는 하나니 cpuCnt값을 1로두고 셌다 근데 문제는 여기서 a->b b->a 로가는 경로가 생길시 a의 경로값이 갱신 되면서 

			if (distance_v[i] != INF) {
				cpuCnt++;

이 부분에서 CPUCNT가 하나더 증가해서 이미센 감염피씨를 한번 더세면서 문제가 틀렸었다 이에 감염된 피씨의 초를 0으로 바꿔주고 cpuCNt의 값을 0으로 바꿔주니 정상적으로 나왔다

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

이 문제의 경우 전형 적인 다익스트라 알고리즘으로 풀 수 있을거 같았다 그 이유는 첫시작 점이 0 그리고 endPoint인 n-1 까지 가는 것으로 정해졌기에

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

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

		if (distanceV[toVertex] < toCost)
			continue;

		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			int nextVertex = edgeList[toVertex][i].second;
			long long nextCost = edgeList[toVertex][i].first;
			if (distanceV[nextVertex] > toCost + nextCost && (canGo[nextVertex] || nextVertex==n-1)) {
				distanceV[nextVertex] = toCost + nextCost;
				djikstra_pq.push({ toCost + nextCost,nextVertex });
			}
		}

	}
}

굳이 플로이드  와샬로 전체 의 거리는 구할 필요가 없기 때문이다 

항상 다익스트라에서 쓰는 로직과 비슷하다 일단 StartVertex를 StarVertex까지의 거리가 0이라 두고 큐에다가 넣는다

그후 edgeList에서  startNode와 연결된 모든 노드들과 계산하여 거리를 구한후 priority queue에 넣는다 이를 반복하면 결국에 마지막 노드까지 가는거리가 최단거리로 완성이 된다.

이문제의 경우 단 djikstra를 풀때 조건이 하나가 추가되는데 해당 vertex의 시야값이 1이면 가지 않는 것이다

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 1234987654321
priority_queue < pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> djikstra_pq;
vector<pair<int, long long>> edgeList[300000];
vector<long long> distanceV(300000);
bool canGo[300000] = { 0, };
int n, m;
void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ toCost,start });

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

		if (distanceV[toVertex] < toCost)
			continue;

		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			int nextVertex = edgeList[toVertex][i].second;
			long long nextCost = edgeList[toVertex][i].first;
			if (distanceV[nextVertex] > toCost + nextCost && (canGo[nextVertex] || nextVertex==n-1)) {
				distanceV[nextVertex] = toCost + nextCost;
				djikstra_pq.push({ toCost + nextCost,nextVertex });
			}
		}

	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> canGo[i];
		canGo[i] = !canGo[i];
	}

	for (int i = 0; i < m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		edgeList[from].push_back({ cost,to });
		edgeList[to].push_back({ cost,from });
	}
	distanceV.assign(n , INF);
	djikstraSolution(0);
	if (distanceV[n - 1] >= INF)
		cout << -1;
	else
		cout << distanceV[n-1];
}

전체 코드는 위와 같다

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

이 문제는 플로이드 워셜 알고리즘을 다룬다
다익스트라는 하나의 점에서 부터 다른 vertex까지의 최단 경로를 구하는 것이라면
플로이드 워셜은 전체 점에서의 최단 경로를 구하는 문제이다

다익스트라 알고리즘의 경우 우선순위 큐에 계속 넣어서 경로의 최솟값들을 소모시키면서 다른 vertex들과의 비용을 업데이트 해줬다.

단 플로이드 워셜 알고리즘의 경우 모든 점을 업데이트 해줘야하므로 dp를 통해 순차 탐색을 진행해준다

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}

핵심 로직은 이부분이다 K라는 경유점을 통해서 i to j 의 값과 기존에 i to j의 값을 비교해서 더작으면 넣어주는게 로직이다 .

#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;

int n;
int dp[101][101];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	int m;
	cin >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				dp[i][j] = 0;
			else
				dp[i][j] = INF;
		}
	}
	for (int i = 0; i < m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		dp[from][to] = min(dp[from][to], cost);
	}
	//k는 경유점
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dp[i][j] == INF) {
				cout << 0 << ' ';
				continue;
			}
			cout << dp[i][j] << ' ';
		}
		cout << '\n';
	}
	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];
}

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

이 문제는 쉽다 일단 다익스트라 알고리즘을 사용하고 간선이 양방향이니 양방향으로 설정해 준다

다익스트라로 각지점의 최단거리를 구해준 후 거리를 정렬하여 범위 안에 있는 아이템에 개수를 더해준 누적값을 구해주면 된다

#include <iostream>
#include <vector>
#include <queue>
#include<algorithm>
#define INT_MAX 2147483647
using namespace std;
int NumOfItem[101];
vector<pair<int, int>> dijkstraV[101];
vector<int> distanceV(101);

void dijkstra(int start) {
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq; // 비용 노드
	pq.push(make_pair(0, start));
	distanceV[start] = 0;
	while (!pq.empty()) {
		int distanceOfTo = pq.top().first;
		int toVertex = pq.top().second;
		pq.pop();

		if (distanceOfTo > distanceV[toVertex]) {
			continue;
		}

		for (int i = 0; i < (int)dijkstraV[toVertex].size(); i++) {
			int cost = distanceOfTo + dijkstraV[toVertex][i].second;
			if (cost < distanceV[dijkstraV[toVertex][i].first]) {
				distanceV[dijkstraV[toVertex][i].first] = cost;
				pq.push(make_pair(cost, dijkstraV[toVertex][i].first));
			}
		}
	}
}

int getNumOfItem(int idx, int n, int m) {
	int sum=0;
	for (int i = 1; i <= n; i++) {
		if (distanceV[i] <= m) {
			sum += NumOfItem[i];
		}
	}
	return sum;
}


int main() {
	
	int n, m, r;
	int maxItem=0;
	cin >> n >> m >> r;
	for (int i = 1; i <= n; i++) {
		cin >> NumOfItem[i];
	}

	int from, to, cost;
	for (int i = 0; i < r; i++) {
		cin >> from >> to >> cost;
		dijkstraV[from].push_back({ to, cost });
		dijkstraV[to].push_back({ from,cost });
	}

	for (int i = 1; i <= n; i++) {
		distanceV.assign(101, INT_MAX);
		dijkstra(i);
		if(maxItem < getNumOfItem(i, n, m))
			maxItem = getNumOfItem(i, n, m);
	}
	cout << maxItem;
}