TIL day 86

2025. 4. 22. 15:15·TIL
목차
  1. 1. 코딩테스트
  2. 2. 언리얼
  3.  

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

1. Recap1 - 1. Server - Client 모델언리얼 엔진은 멀티플레이 게임에서 Server-Client 구조를 사용한다.서버만이 결정을 내리며, Authority를 가진다.클라이언트끼리는 직접 통신하지 않는다.클라이언트에서

gbleem.tistory.com

 

 

'TIL' 카테고리의 다른 글

TIL day 94  (0) 2025.05.02
TIL day 87  (0) 2025.04.23
TIL day 85  (0) 2025.04.21
TIL day 79  (0) 2025.04.11
TIL day 78  (0) 2025.04.10
  1. 1. 코딩테스트
  2. 2. 언리얼
  3.  
'TIL' 카테고리의 다른 글
  • TIL day 94
  • TIL day 87
  • TIL day 85
  • TIL day 79
gbleem
gbleem
gbleem 님의 블로그 입니다.
  • gbleem
    gbleem 님의 블로그
    gbleem
  • 전체
    오늘
    어제
    • 분류 전체보기 (184)
      • Unreal Engine (73)
      • C++ (19)
      • 알고리즘(코딩테스트) (27)
      • TIL (60)
      • CS (4)
      • 툴 (1)
  • 블로그 메뉴

    • 홈
    • 카테고리
  • 링크

    • 과제용 깃허브
    • 깃허브
    • velog
  • 공지사항

  • 인기 글

  • 태그

    character animation
    motion matching
    DP
    additive animation
    Vector
    BFS
    map을 vector로 복사
    템플릿
    applydamage
    const
    enhanced input system
    actor 클래스
    매크로 지정자
    blend pose
    상속
    addonscreendebugmessage
    C++
    싱글턴
    cin함수
    gamestate
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
gbleem
TIL day 86

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.