TIL day 86

1. 코딩테스트

---

오늘은 class 4의 특정한 최단 경로 문제를 풀었다.

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

 

문제를 보고 다익스트라 문제일 것이라는 생각이 들었다.

이유는 

• 가중치가 존재하고,
• 최단 경로를 구해야 했기 때문이다.

아직 다익스트라 코드에 익숙하지 않아서 기존에 공부한 코드를 좀 참고하여 풀었다. 

추가로 다익스트라 문제를 몇 개 풀었는데, 배열로는 시간초과가 발생하는 문제가 있어서 우선순위 큐 이용한 방식에 익숙해지면 될 것 같다.

 

코드 해설

• 이 문제에 있어서는 추가적으로 무조건 지나가야할 정점이 2개가 주어진다. 
• 이 정점을 모두 지나면서 최단경로를 구해야하기 때문에 아래와 같은 과정을 수행했다.
• 다익스트라 하는 함수를 시작점을 매개변수로 넣어 여러번 수행할 수 있게 하였다.
• 이 문제에서는 1 -> v1 -> v2 / 1 -> v2 -> v1 이런 두가지 방식이 있을 수 있기 때문이다.
• 추가)
  • 마지막에 문제가 89% 정도에서 틀린 경우가 있었는데, 이 경우 INF 값을 너무 크게 잡아서 overflow가 발생하는 문제였다.
  • 그래서 INF의 값을 3으로 나눠서 overflow를 방지해 주어서 해결하였다.

정답 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<pair<int,int>> adj[802];
const int INF = 1e9/3;
int dist[802];
int n, e;
int v1, v2;
int answer1 = 0;
int answer2 = 0;

void Dijk(int st)
{
	fill(dist, dist + n + 1, INF);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;

	dist[st] = 0;
	pq.push({ dist[st], st });

	while (!pq.empty())
	{
		auto cur = pq.top();
		pq.pop();

		if (dist[cur.second] != cur.first)
			continue;
		for (auto nxt : adj[cur.second])
		{
			if (dist[nxt.second] <= dist[cur.second] + nxt.first)
				continue;

			dist[nxt.second] = dist[cur.second] + nxt.first;
			pq.push({ dist[nxt.second], nxt.second });
		}
	}
}

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

	cin >> n >> e;

	for (int i = 0; i < e; ++i)
	{
		int a, b, c;
		cin >> a >> b >> c;
		
		adj[a].push_back({ c, b });
		adj[b].push_back({ c, a });		
	}
	cin >> v1 >> v2;

	Dijk(1);		
	answer1 += dist[v1];
	Dijk(v1);
	answer1 += dist[v2];
	Dijk(v2);
	answer1 += dist[n];

	Dijk(1);
	answer2 += dist[v2];
	Dijk(v2);
	answer2 += dist[v1];
	Dijk(v1);
	answer2 += dist[n];

	int ans = min(answer1, answer2);
	if (ans >= INF)
		cout << -1;
	else
		cout << ans;
}

 

 

2. 언리얼

---

오늘은 지난번에 다 공부하지 못했던, 언리얼 멀티플레이 최적화 관련 강의를 듣고 공부를 진행하였습니다.

 

강의는 다 들었고, 1강 (recap), 2강(큰 데이터 리플리케이션 과 RPC최적화) 에 대한 내용을 정리하였습니다.

https://gbleem.tistory.com/166

Unreal Engine - 멀티플레이 네트워크 최적화 1