✅ 한 것들

---

• 백준
• Cherno Game Engine Course

⚔️ 백준

---

• 1012 유기농 배추

6087 레이저 통신

#include"6087.h"
using namespace std;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;

namespace
{
	int w, h;
	vvc tmap;
	vvvi mcount;
	vi sp = { -1,-1 };
	vi tp;
	vvi dirArr = { {1,0},{-1,0},{0,1},{0,-1} };

	bool isValid(int i, int j)
	{
		return 0 <= i && i < h && 0 <= j && j < w;
	}

	// 0 1 > -1 0, 1 0
	// 위아래로 가고 있었다면 좌우, 좌우면 위아래로

	// 예외 : 좀 더 많은 거울을 지났더라도, 다른 방향이라면 최소일 경우 존재?

	void bfs(int count, int i, int j, int dirIdx)
	{
		if (!isValid(i, j)) return;
		if (tmap[i][j] == '*') return;
		if (mcount[i][j][dirIdx] <= count) return;
		mcount[i][j][dirIdx] = count;
		if (i == tp[0] && j == tp[1]) return;

		// 일단 가던 방향으로 보내보고
		vi dir = dirArr[dirIdx];
		bfs(count, i + dir[0], j + dir[1], dirIdx);
		if (dir[0] == 0) // 좌우로 가고 있었다면 위아래로 바꾼다
		{
			dir = dirArr[0];
			bfs(count + 1, i + dir[0], j + dir[1], 0);
			dir = dirArr[1];
			bfs(count + 1, i + dir[0], j + dir[1], 1);
		}
		else
		{
			dir = dirArr[2];
			bfs(count + 1, i + dir[0], j + dir[1], 2);
			dir = dirArr[3];
			bfs(count + 1, i + dir[0], j + dir[1], 3);
		}
	}
}


void B6087::Solution()
{
	cin >> w >> h;
	tmap = vvc(h, vector<char>(w));
	mcount = vvvi(h, vvi(w, vi(4,10001)));
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			cin >> tmap[i][j];
			if (tmap[i][j] == 'C')
			{
				if (sp[0] == -1) sp = { i,j };
				else tp = { i,j };
			}
		}
	}

	for (int idx=0; idx<4; idx++)
	{
		int newi = sp[0] + dirArr[idx][0];
		int newj = sp[1] + dirArr[idx][1];
		bfs(0, newi, newj, idx);
	}

	vi tpm = mcount[tp[0]][tp[1]];
	cout << *min_element(tpm.begin(),tpm.end());
}

• 재귀라 시간이 오래 걸린 것도 있긴 했는데
• bfs라고 생각해놓고 stack을 써버려서 dfs 해버리고 어마어마한 비효율 발생

#include"6087.h"
using namespace std;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;

void B6087::Solution()
{
	cin.tie(nullptr)->sync_with_stdio(false);
	vi sp = { -1,-1 };
	vi tp;
	vvi dirArr = { {1,0},{-1,0},{0,1},{0,-1} };

	int w, h;
	cin >> w >> h;

	vvc tmap = vvc(h, vector<char>(w));
	vvvi mcount = vvvi(h, vvi(w, vi(4, 10001)));
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			cin >> tmap[i][j];
			if (tmap[i][j] == 'C')
			{
				if (sp[0] == -1) sp = { i,j };
				else tp = { i,j };
			}
		}
	}

	deque<vi> dq;
	for (int idx : {0, 1, 2, 3})
	{
		mcount[sp[0]][sp[1]][idx] = 0;
		vi dir = dirArr[idx];
		dq.push_front({ sp[0],sp[1],idx });
	}

	while (!dq.empty())
	{
		int i = dq.front()[0];
		int j = dq.front()[1];
		int dirIdx = dq.front()[2];
		vi dir = dirArr[dirIdx];
		dq.pop_front();

		for (int newDirIdx : {0, 1, 2, 3})
		{
			vi newDir = dirArr[newDirIdx];
			int newi = i + newDir[0];
			int newj = j + newDir[1];
			if (newi < 0 || newj < 0 || h <= newi || w <= newj) continue;
			if (tmap[newi][newj] == '*') continue;

			int newCount = mcount[i][j][dirIdx] + 1;
			if (dirIdx == newDirIdx) newCount--;

			if (mcount[newi][newj][newDirIdx] <= newCount) continue;
			mcount[newi][newj][newDirIdx] = newCount;
			if (tmap[newi][newj] == 'C') continue;

			if(dirIdx == newDirIdx) dq.push_front({newi,newj,dirIdx});
			else dq.push_back({ newi,newj,newDirIdx });
		}
	}

	vi tpm = mcount[tp[0]][tp[1]];
	cout << *min_element(tpm.begin(), tpm.end());
}

• 스택으로 했더니 240ms → 8ms로 줄어듦
• 다시 deque로 0-1 bfs 해서 8ms → 4ms로 줄임
• (dir[0] == 0) ^ (newDir[0] == 0)로 수평인지 확인했었는데, 필요없었다. 같을 때 비용처리만 따로 하면 됨. 어차피 반대편으로 가는 건 비용 조건 때문에 걸러지기 때문.

1916 최소비용 구하기

#include"1916.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;

void B1916::Solution()
{
	int N, M, start, end, edgeCost;
	cin >> N >> M;
	vvvi g = vvvi(N+1);
	vl cost = vl(N+1, 1000 * 100000);
	while (M--)
	{
		cin >> start >> end >> edgeCost;
		g[start].push_back({ edgeCost, end });
	}
	cin >> start >> end;
	priority_queue<vl, vvl, greater<vl>> pq;
	pq.push({0,start}); // 최종 비용, 도착점
	cost[start] = 0;

	// 정점 빼서 간선들 봤을 때 최솟값이 변경됐다면
	// 거기서 다시 간선들 훑어서 최소 우선순위 큐에 넣어준다
	while (!pq.empty())
	{
		ll d = pq.top()[0];
		ll n = pq.top()[1];
		pq.pop();
		if (d != cost[n]) continue;
		for (vi e : g[n])
		{
			if (d + e[0] >= cost[e[1]]) continue;
			cost[e[1]] = d + e[0];
			pq.push({ d + e[0], e[1] });
		}
	}

	cout << cost[end];
}

풀긴했는데 또 시간이 안 좋아서 다시 풀기

#include<vector>
#include<iostream>
#include<queue>
#include<tuple>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<vector<pii>> vvp;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
	int N, M, start, end, edgeCost;
	cin >> N >> M;
	vvp graph = vvp(N+1);
	vi cost = vi(N + 1, 1000 * 100000);
	while (M--)
	{
		cin >> start >> end >> edgeCost;
		graph[start].push_back({ edgeCost, end });
	}
	cin >> start >> end;

	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({ 0, start });
	cost[start] = 0;

	while (!pq.empty())
	{
		int dist, node;
		tie(dist, node) = pq.top();
		pq.pop();
		if (dist != cost[node]) continue;
		for (pii edge : graph[node])
		{
			int totalCost = edge.first + cost[node];
			int nextNode = edge.second;
			if (cost[nextNode] <= totalCost) continue;
			cost[nextNode] = totalCost;
			pq.push({ totalCost, nextNode });
		}
	}

	cout << cost[end];
}

메모리도 시간도 남들처럼 나왔다

• long long 대신 int
  • int는 최대 자리수가 10^9라서, 10^5 * 10^3인 문제의 조건을 충분히 커버 가능
• vector 대신 pair로 쓰는게 더 빠르다는듯

🎞️ Cherno Game Engine Course

---

DESIGNING our GAME ENGINE

앞으로 만들 기능들

• Entry Point : 엔진 켰을 때 실행되는 것
• Application Layer : 생명 주기나 이벤트같은 거 담당
• Window Layer
  • 프로그램 보여주는 창
  • Input이나 Event 대응해야 함
  • EventManager가 Event가 오면 Application Layer에 전달하거나 상태를 읽거나 해야 함
• Renderer : 그래픽을 화면에 뿌린다
• Render API abstraction : OpenGL, DirectX 등 멀티 플랫폼 지원할 것
  • 그래픽 API마다 효율적으로 짜려면 달라져야 하는 것도 있어서 무조건 다 추상화하진 않을거
• Debugging support
  • logging, profiling 등 visual studio에서만 말고 컴퓨터 상관없이 돌아가는 디버그 기능
  • 디버그 용으로만 돌아가는 코드도 구현
• Scripting language : c++ 대신 메모리 신경 안 쓰고 Lua, csharp 등 쓸 수 있게
• Memory Systems : 메모리 할당, 추적
• Entity - Component Systems (ECS)
• Physics
• File I/O, VFS (virtual file system)
• Build System
• 엔진에 맞는 3d model의 custom format
• hot - swabbable asset : 포토샵에서 편집하면 바로 업뎃