코딩생존기

오늘은 Instancing과 Culling에 대해 복습해보고 예제코드를 분석해보자

우선 Instancing이 왜 필요할까에 대해 생각해보자. 각각의 오브젝트를 개별로 그려준다고 했을 때, 똑같은 오브젝트가 있더라도 다른 오브젝트가 그려주고 다시 똑같은 오브젝트를 그려준다고 하면 그려주기 위한 비용이 다시 생기기 때문에

드로우콜이 많이 발생한다. 효율적으로 그려주기 위해서는 같은 물체라면 한번에 다 그려주고 다른 오브젝트를 그려주는 것이 좋다. 이때 같은 물체라는 것은 같은 쉐이더와 머테리얼로 그려주는 물체를 의미한다.

우선 예제코드를 실행시켜보자. 실행화면 위쪽에 보면 125개의 물체 중에 13개만 보이고 있다는 것을 알 수 있다. 여기서 만약 2번을 눌러주면 인스턴싱모드가 꺼지면서 125개가 다 그려지며 프레임이 낮아지는 것을 볼 수 있다. 이때 13개가 보인다는 것은 컬링과 관련이 있다.

이때 같은 물체에서 달라지는 부분은 position과 같은 부분으로 이 연산은 쉐이더 코드의 VS부분의 구조체를 보면 된다. 아래에  변수가 VS단계에 입력으로 들어오는 부분에 인스턴싱관련된 부분이다.

struct VertexIn
{
    float3 PosL     : POSITION;
    float3 NormalL  : NORMAL;
    float2 Tex      : TEXCOORD;
    // 인스턴싱
    row_major float4x4 World  : WORLD;
    float4 Color    : COLOR;
    uint InstanceId : SV_InstanceID;
};

코드 상에서는 Vertex부분에 쉐이더코드에 맞게 묘사해주도록 변수가 맞춰져있다.

typedef struct D3D11_INPUT_ELEMENT_DESC
{
    LPCSTR SemanticName;
    UINT SemanticIndex;
    DXGI_FORMAT Format;
    UINT InputSlot;			//인스턴싱일때 구분해줘야함
    UINT AlignedByteOffset;
    D3D11_INPUT_CLASSIFICATION InputSlotClass;
    UINT InstanceDataStepRate;
} 	D3D11_INPUT_ELEMENT_DESC;
    
static ComPtr<ID3D11InputLayout> InstancedBasic32;
    
const D3D11_INPUT_ELEMENT_DESC InputLayoutDesc::InstancedBasic32[8] =
{
	{"POSITION", 0, DXGI_FORMAT_R32G32B32_FLOAT, 0, 0, D3D11_INPUT_PER_VERTEX_DATA, 0},
	{"NORMAL",   0, DXGI_FORMAT_R32G32B32_FLOAT, 0, 12, D3D11_INPUT_PER_VERTEX_DATA, 0},
	{"TEXCOORD", 0, DXGI_FORMAT_R32G32_FLOAT, 0, 24, D3D11_INPUT_PER_VERTEX_DATA, 0},
	{ "WORLD", 0, DXGI_FORMAT_R32G32B32A32_FLOAT, 1, 0, D3D11_INPUT_PER_INSTANCE_DATA, 1 },
	{ "WORLD", 1, DXGI_FORMAT_R32G32B32A32_FLOAT, 1, 16, D3D11_INPUT_PER_INSTANCE_DATA, 1 },
	{ "WORLD", 2, DXGI_FORMAT_R32G32B32A32_FLOAT, 1, 32, D3D11_INPUT_PER_INSTANCE_DATA, 1 },
	{ "WORLD", 3, DXGI_FORMAT_R32G32B32A32_FLOAT, 1, 48, D3D11_INPUT_PER_INSTANCE_DATA, 1 },
	{ "COLOR", 0, DXGI_FORMAT_R32G32B32A32_FLOAT, 1, 64,  D3D11_INPUT_PER_INSTANCE_DATA, 1 }
};

이때 D3D11_INPUT_PER_INSTANCE_DATA 뒤에 나오는 1이라는 수는 instance data step이라는 옵션으로 instance별 자료 원소 하나당 그릴 instance의 개수이다. 이렇게 묘사해준 값을 IA단계에서 넘겨줘야한다. IASetVertexBuffers에서 2번째 매개변수를 2로 설정해주고 있는 것을 볼 수 있다. 이 2는 2가지 값을 넘겨주고 있다는 것인데 이 2가지 값은 SkullVertexBuffer와 InstanceBuffer이다.

이렇게 해준다음 마지막에 DrawIndexedInstanced로 그려주면 된다. 이때 몇개를 그려줄지에 대한 값도 넘겨줘야한다.

ID3D11Buffer* vbs[2] = { _skullVB.Get(), _instancedBuffer.Get() };

_deviceContext->IASetVertexBuffers(0, 2, vbs, stride, offset);
_deviceContext->IASetIndexBuffer(_skullIB.Get(), DXGI_FORMAT_R32_UINT, 0);

_deviceContext->DrawIndexedInstanced(_skullIndexCount, _visibleObjectCount, 0, 0, 0);

이때 InstanceBuffer를 묘사해주는 부분을 가보면 InstanceData를 통해 데이터를 채워주고 이 값에 따라 InstanceBuffer를 채워준다.

void InstancingAndCullingDemo::BuildInstancedBuffer()
{
	const int32 n = 5;
	_instancedData.resize(n * n * n);

	float width = 200.0f;
	float height = 200.0f;
	float depth = 200.0f;

	float x = -0.5f * width;
	float y = -0.5f * height;
	float z = -0.5f * depth;
	float dx = width / (n - 1);
	float dy = height / (n - 1);
	float dz = depth / (n - 1);

	for (int k = 0; k < n; ++k)
	{
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				// Position instanced along a 3D grid.
				_instancedData[k * n * n + i * n + j].World = XMFLOAT4X4(
					1.0f, 0.0f, 0.0f, 0.0f,
					0.0f, 1.0f, 0.0f, 0.0f,
					0.0f, 0.0f, 1.0f, 0.0f,
					x + j * dx, y + i * dy, z + k * dz, 1.0f);

				// Random color.
				_instancedData[k * n * n + i * n + j].Color.x = MathHelper::RandF(0.0f, 1.0f);
				_instancedData[k * n * n + i * n + j].Color.y = MathHelper::RandF(0.0f, 1.0f);
				_instancedData[k * n * n + i * n + j].Color.z = MathHelper::RandF(0.0f, 1.0f);
				_instancedData[k * n * n + i * n + j].Color.w = 1.0f;
			}
		}
	}

	D3D11_BUFFER_DESC vbd;
	vbd.Usage = D3D11_USAGE_DYNAMIC;
	vbd.ByteWidth = sizeof(InstancedData) * _instancedData.size();
	vbd.BindFlags = D3D11_BIND_VERTEX_BUFFER;
	vbd.CPUAccessFlags = D3D11_CPU_ACCESS_WRITE;
	vbd.MiscFlags = 0;
	vbd.StructureByteStride = 0;

	HR(_device->CreateBuffer(&vbd, 0, _instancedBuffer.GetAddressOf()));
}

 Rasterizer에서 실행되는 것으로 영역에서 벗어난 부분이라면 보이지 않게 하는 데 이 부분에서 컬링이 실행되긴한다.

하지만 그 앞 단계까지에서 그려줄 애들은 이미 계산을 해준 상태이기 때문에 만약 안그려줘도 되는 아이라면 CPU단에서 처리해주는 것이 효율적일 것이다. 이를 해주는 것이 절두체 컬링(Frustum Culling)이다.

아래 코드를 보면 2개의 변수가 각각 해골이 그려져있는 영역과 카메라의 절두체 영역으로 절두체 컬링을 위한 것이다. 

//해골 영역
BoundingBox _skullBox;
//절두체 영역
BoundingFrustum _camFrustum;

이를 통해 카메라의 절두체 안에 있는지 체크하고 만약 있다면 그려주는 코드는 UpdateScene에 있다.

void InstancingAndCullingDemo::UpdateScene(float dt)
{
if (_frustumCullingEnabled)
{
	XMVECTOR detView = XMMatrixDeterminant(_camera.View());
	XMMATRIX invView = XMMatrixInverse(&detView, _camera.View());

	D3D11_MAPPED_SUBRESOURCE mappedData;
	_deviceContext->Map(_instancedBuffer.Get(), 0, D3D11_MAP_WRITE_DISCARD, 0, &mappedData);

	InstancedData* dataView = reinterpret_cast<InstancedData*>(mappedData.pData);

	for (uint32 i = 0; i < _instancedData.size(); ++i)
	{
		XMMATRIX W = ::XMLoadFloat4x4(&_instancedData[i].World);
		XMVECTOR D = ::XMMatrixDeterminant(W);
		XMMATRIX invWorld = ::XMMatrixInverse(&D, W);

		// View space to the object's local space.
		XMMATRIX toLocal = ::XMMatrixMultiply(invView, invWorld);

		// Decompose the matrix into its individual parts.
		XMVECTOR scale;
		XMVECTOR rotQuat;
		XMVECTOR translation;
		::XMMatrixDecompose(&scale, &rotQuat, &translation, toLocal);

		// Transform the camera frustum from view space to the object's local space.
		BoundingFrustum localspaceFrustum;

		_camFrustum.Transform(localspaceFrustum, XMVectorGetX(scale), rotQuat, translation);
		//XNA::TransformFrustum(&localspaceFrustum, &_camFrustum, );

		// 그려줘야하는지 체크
		if (localspaceFrustum.Contains(_skullBox))
		{
			// Write the instance data to dynamic VB of the visible objects.
			dataView[_visibleObjectCount++] = _instancedData[i];
		}
	}

	_deviceContext->Unmap(_instancedBuffer.Get(), 0);
}
}

절두체 판단에서는 한면에 대해서 이 물체가 절두체 이전에 있는지 이후에 있는지를 통해 그려주는지 판단해주고 이를 6면에 대해서 해주면 된다. 이 중에 하나라도 통과하지 못하면 그려주지 않는다.

Tessellation영역은 파이프라인에서 Hull Shader,Tessellator, Domain Shader를 합친 것이다. 이때 Hull Shader와 Domain Shader는 쉐이더 코드를 통해 사용할 수 있고 Tessellator는 옵션을 통해 사용해줄 수 있다.

Tessellatoion은 기하 구조를 더 작은 삼각형들로 분할하고 새로 생긴 정점들의 위치를 적절한 방식으로 조절해주는 것이다. 주로 지형 지물, 터레인에서 많이 사용되고 특히 GPU에서의 LOD(멀수록 퀄리티 떨어져 보임)연산에서 연관이 많다.

이 Tessellatoion을 사용할 때는 삼각형을 매개변수로 사용하는 것이 아닌 D3D11_PRIMITIVE_TOPOLOGY_TRIANGLELIST 이런 변수를 입력으로 받는다. 이것은 4개의 제어점으로 이것을 분할해서 사용하는 것이다. Tessellation은 이 제어점을 기준으로 하는 패치가 기본 단위로 연산이 이루어 진다.

예제코드를 실행하게 되면 멀어질수록 삼각형이 적어지고 가까이 갈수록 삼각형의 개수가 많아져서 세밀하게 보이게 된다.

쉐이더 코드를 살펴보면 기존의 VS와 PS단계에서 추가된 코드를 볼 수 있다. 우선 Hull Shader 코드에서  각 Tessellation의 기본 단위인 패치마다 실행되는 ConstantHS 단계를 먼저 살펴보자. 이 단계에서 얼마나 더 세분화해줄 지에 관련된 계수를 출력해준다. 이 계수에 해당하는 변수는 각 변의 세분정도를 나타내는 EdgeTess와 내부의 분할정도를 나타내는 InsideTess가 있다.

struct PatchTess
{
	float EdgeTess[4]   : SV_TessFactor;
	float InsideTess[2] : SV_InsideTessFactor;
};

PatchTess ConstantHS(InputPatch<VertexOut, 4> patch, uint patchID : SV_PrimitiveID)
{
	PatchTess pt;

	//거리계산 - 패치들의 평균값
	float3 centerL = 0.25f * (patch[0].PosL + patch[1].PosL + patch[2].PosL + patch[3].PosL);
	float3 centerW = mul(float4(centerL, 1.0f), gWorld).xyz;

	//패치들과 카메라간의 거리 파악
	float d = distance(centerW, gEyePosW);


	//20(최소)~100(최대)사이
	const float d0 = 20.0f;
	const float d1 = 100.0f;
	float tess = 64.0f * saturate((d1 - d) / (d1 - d0));

	//각 변의 세분정도
	pt.EdgeTess[0] = tess;
	pt.EdgeTess[1] = tess;
	pt.EdgeTess[2] = tess;
	pt.EdgeTess[3] = tess;

	//내부의 분할정도
	pt.InsideTess[0] = tess;
	pt.InsideTess[1] = tess;

	return pt;
}

이 다음 단계는 출력하는 제어점마다 한번씩 실행되는 HS 단계로 표면을 어떻게 표현할지를 정해준다. 현재는 그냥 통과 시켜주고 있지만 설정해줄 수 있는 부분이 많다.

struct HullOut
{
	float3 PosL : POSITION;
};

[domain("quad")]
[partitioning("integer")]
[outputtopology("triangle_cw")]
[outputcontrolpoints(4)]
[patchconstantfunc("ConstantHS")]
[maxtessfactor(64.0f)]
//출력하는 제어점마다 한번씩- 표면
HullOut HS(InputPatch<VertexOut, 4> p,
	uint i : SV_OutputControlPointID,
	uint patchId : SV_PrimitiveID)
{
	HullOut hout;

	hout.PosL = p[i].PosL;

	return hout;
}

그 다음이 Tessellator 단계이다. 이 단계에서는 쉐이더에서 정해준 값에 따라 분할이 일어나는 단계로 GPU가 해주는 작업이고 Domain shader단계로 넘어가게 된다. 이 단계에서는 동적으로 생성과 기존 정점의 행렬연산을 해주게 된다. Tesselation의 VS단계라고 보면 된다.

struct DomainOut
{
	float4 PosH : SV_POSITION;
};

// The domain shader is called for every vertex created by the tessellator.  
// It is like the vertex shader after tessellation.
[domain("quad")]
DomainOut DS(PatchTess patchTess,
	float2 uv : SV_DomainLocation,
	const OutputPatch<HullOut, 4> quad)
{
	DomainOut dout;

	// Bilinear interpolation.
	float3 v1 = lerp(quad[0].PosL, quad[1].PosL, uv.x);
	float3 v2 = lerp(quad[2].PosL, quad[3].PosL, uv.x);
	float3 p = lerp(v1, v2, uv.y);

	// Displacement mapping
	p.y = 0.3f * (p.z * sin(p.x) + p.x * cos(p.z));

	dout.PosH = mul(float4(p, 1.0f), gWorldViewProj);

	return dout;
}

Tesselation은 GS단계와 비슷하지만 하나의 물체가 있는 상태에서 분할하는 느낌이고 GS단계는 별도의 물체를 생성할 수도 있는 느낌이라고 생각하면 된다. GS는 파티클이나 빌보드에 많이 사용되고 Tesselation은 Terrain같은 지형지물에 많이 사용한다.

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

세가지 연산을 적절히 사용해서 최소 연산 수를 통해 1로 만드는 연산을 해야하는데 이때 점화식을 만들어서 해보자.

우선 1을 뺐을때와 2로 나눴을때 3으로 나눴을때의 연산 수 비교해서 최소값 배열을 2부터n까지 계산해두고 필요한 수를 꺼내서 사용하면 된다.

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<int>dp(n + 1);

	dp[1] = 0;

	for (int i = 2; i <= n; i++)
	{
		//우선 1빼보기
		dp[i] = dp[i - 1] + 1;
		if (i % 2 == 0)
		{
			//1뺐을때와 2로 나누었을때 비교
			dp[i] = min(dp[i], dp[i / 2] + 1);
		}
		if (i % 3 == 0)
		{
			//1뺐을때와 3로 나누었을때 비교
			dp[i] = min(dp[i], dp[i / 3] + 1);
		}
	}

	cout << dp[n];
}

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

삼각형을 2차원 벡터를 통해 입력받고 이 벡터와 크기가 같은 벡터를  선언해주고 이 벡터에 누적합을 계산해서 넣어주면 된다. 이때 현재 층에서 내려갈 때 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서 선택해서 내려가야하는데  내려가있는 입장에서 생각해보면 경우를 나눠서 계산을 해줘야한다.

가장 왼쪽의 경우에는 x-1, y 위치의 원소에 자신의 값을 더해주면 된다.

가장 오른쪽의 경우에는 x-1, y-1 위치의 값에 자신의 값을 더해주면 된다.

가운데의 경우에는  x-1,y-1 와 x-1,y위치 중에 큰 값과 자신의 값을 저해주면 된다.

마지막행에서 최대값을 찾아서 출력해주면 된다.

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<vector<int>> triangle(n, vector<int>(n, 0));


	for (int i = 0; i < n; i++)
	{
		for (int j =0; j<=i; j++)
		{
			cin >> triangle[i][j];
		}
		
	}
	
	vector<vector<int>> dp(n, vector<int>(n, 0));

	dp[0][0] = triangle[0][0];

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			//가장 왼쪽
			if (j == 0)
			{
				dp[i][j] = dp[i - 1][j] + triangle[i][j];
			}
			else if (j == i)	//가장 오른쪽
			{
				dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
			}
			else      //가운데
			{
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
			}
		}
	}

	int result = 0;
	for (int i = 0; i < n; i++)
	{
		result = max(dp[n - 1][i], result);
	}

	cout << result << "\n";
}

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

먼저 모든 집의 RGB에 해당하는 비용 값을 벡터를 통해 입력받고 n-1까지의 합벡터를 채워주면 되는데 이때 RGB를 더할 때 문제에서 각 집을 칠할 때 이전 집과 같은 색을 사용할 수 없으므로, 이 조건을 만족하며 비용을 최소화하는 선택만을 하도록 하여 자신을 제외한 이전에 계산된 비용중에서 최소값과 자신의 비용을 더한 것이 현재 위치의 합 배열이 값으로 계산해주면 된다.

정답코드

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

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<vector<int>> cost(n, vector<int>(3));
	vector<vector<int>> dp(n, vector<int>(3));

	//RGB입력받기
	for (int i = 0; i < n; i++)
	{
		cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
	}

	// 첫 번째 집 초기화
	dp[0][0] = cost[0][0];
	dp[0][1] = cost[0][1];
	dp[0][2] = cost[0][2];

	//미리 모든 경우의수 계산
	for (int i = 1; i < n; i++)
	{
		dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
		dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
		dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
	}

	int result = min({ dp[n - 1][0], dp[n - 1][1], dp[n - 1][2] });
	cout << result << endl;

	return 0;
}

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

케이스 수만큼 반복을 해주는데 이때 그래프 크기를 입력받고 이에 맞게 assign함수를 통해 벡터를 m,n의 크기로 초기화해주고 배추가 있는 부분만 1로 수정해준다. 그리고 그래프를 전체 순회하면서 1인부분을 만난다면 BFS방식으로 순회하면서 방문처리를 해준다. 그리고 모두 방문처리가 완료되면 true를 반환해서 result값을 1 더해주고 이 result에 1이 몇번 더해졌는지 출력해주면 된다. 

정답코드

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

using namespace std;

int n, m;
bool BFS(int x, int y);
vector<vector<int>> graph;
vector < vector<bool> >visited;
int main()
{
	int t;
	cin >> t;

	for (int i = 0; i < t; i++)
	{
		m = 0, n = 0;
		int k;

		cin >> m >> n >> k;

		graph.assign(m, vector<int>(n, 0));
		visited.assign(m, vector<bool>(n, false));

		//배추 입력
		for (int i = 0; i < k; i++)
		{
			int X, Y;
			cin >> X >> Y;

			graph[X][Y] = 1;
		}

		int result = 0;

		//그래프 순회
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (graph[i][j] == 1 && !visited[i][j])
				{
					if (BFS(i, j)) result++;
				}
			}
		}

		cout << result << "\n";
	}
}

bool BFS(int x, int y)
{
	//상하좌우
	int nx[4] = { -1,1,0,0 };
	int ny[4] = { 0,0,-1,1 };

	queue<pair<int, int>> q;
	q.push({ x,y });
	visited[x][y] = true;

	while (!q.empty())
	{
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int next_x = cur_x + nx[i];
			int next_y = cur_y + ny[i];

			if (next_x >= 0 && next_x < m && next_y >= 0 && next_y < n)
			{
				if (graph[next_x][next_y] == 1 && !visited[next_x][next_y])
				{
					visited[next_x][next_y] = true;
					q.push({ next_x,next_y });
				}
			}
		}
	}

	return true;
}

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

그래프를 입력받고 그래프 전체를 순회하는데 방문하지 않았고 1이라면 집이 있기 때문에 여기서부터 BFS방식으로 순회하면서 더 이어진 주택이 없을 때까지 순회한다. 그리고 이 과정에서 들린 집개수를 카운트해서 반환해주면 된다.

정답코드

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

using namespace std;

int n;
int BFS(int x,int y);
vector<vector<int>> house;
vector<vector<bool>> visited;
int main()
{
	cin >> n;

	house.resize(n, vector<int>(n));
	visited.resize(n, vector<bool>(n,false));

	//그래프 입력
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			char c;
			cin >> c;
			//문자열-> 숫자
			house[i][j] = c - '0';
		}
	}

	vector<int> answer;

	//그래프 순회
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!visited[i][j] && house[i][j] == 1)
			{
				int h_cnt = BFS(i, j);
				answer.push_back(h_cnt);
			}
		}
	}
	
	//오름차순 정렬
	sort(answer.begin(), answer.end());
	cout << answer.size() << "\n";
	for (int i = 0; i < answer.size(); i++)
	{
		cout << answer[i] << "\n";
	}
}

int BFS(int x,int y)
{
	//상하좌우
	int nx[4] = { -1,1,0,0 };
	int ny[4] = { 0,0,-1,1 };

	queue<pair<int, int>> q;


	q.push({ x,y });
	visited[x][y] = true;

	int cnt = 1;

	//현재위치에서 이어져 있는 주택이 있으면 연결
	while (!q.empty())
	{
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int next_x = cur_x + nx[i];
			int next_y = cur_y + ny[i];

			if (next_x >= 0 && next_x < n && next_y>=0 && next_y < n)
			{
				if (house[next_x][next_y] == 1 && !visited[next_x][next_y])
				{
					q.push({ next_x,next_y });
					visited[next_x][next_y] = true;
					cnt++;
				}
			}
		}
	}

	return cnt;	
}

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

그래프입력을 받고 DFS를 통해 순회하면서 시작노드를 제외하고 전역변수를 통해 카운트하면서 얼마나 순회하는지 계산하면 된다. 

정답코드

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


void DFS(int node);
vector<vector<int>> computers;
vector<bool> visited;
int cnt = 0;
int main()
{
	int n, m;
	cin >> n >> m;

	computers.resize(n + 1);
	visited.resize(n + 1);

	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		computers[u].push_back(v);
		computers[v].push_back(u);
	}

	DFS(1);

	cout << cnt << "\n";
}

void DFS(int node)
{
	visited[node] = true;
	
	for (int i : computers[node])
	{
		if (!visited[i])
		{
			cnt++;
			DFS(i);
		}
	}
}

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

그래프 입력을 받고 각 정점벡터를 내림차순으로 정렬한 다음에 의사코드에 나와있는 코드와 같이 구현해준다.

이때 전역변수를 사용하여 방문순서를 기록해주도록 하자.

정답코드

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

using namespace std;

void DFS(int node);
vector<vector<int>> graph;
vector<int> visited;
int order = 1;
int main()
{
	int n, m, r;
	cin >> n >> m >> r;

	graph.resize(n + 1);
	visited.resize(n + 1);
	fill(visited.begin(), visited.end(), 0);

	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	// 인접 정점 내림차순으로 정렬
	for (int i = 1; i <= n; i++) {
		sort(graph[i].rbegin(), graph[i].rend());
	}

	DFS(r);

	for (int i = 1; i <= n; i++)
	{
		cout << visited[i] << "\n";
	}
}

void DFS(int node)
{
	visited[node] = order++;
	for (int next : graph[node]) {
		if (!visited[next]) {
			DFS(next);
		}
	}
}

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

A번째 도시에서 B번째 도시까지 최소 비용을 출력해줘야한다. 다익스트라 알고리즘을 가지고 풀어보았다. 우선 시작점에서 모든 경로로 가는 최소비용을 계산해두고 계산된 도착지까지의 최소 비용을 출력해주면 된다. 

다익스트라 계산과정에서 priority_queue를 사용하는 이유는, 다익스트라 알고리즘에서 가장 짧은 경로를 가진 정점을 빠르게 선택하기 위해서이다.

정답코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

typedef pair<int, int> edge;
//인접그래프
vector<vector<edge>> graph;
//거리
vector<int> mdistance;
//방문여부
vector<bool> visited;

int dijkstra(int start, int end);

int  main()
{
	int v, e;

	cin >> v >> e;

	graph.resize(v + 1);
	mdistance.resize(v + 1);
	fill(mdistance.begin(), mdistance.end(), INT_MAX);
	visited.resize(v + 1);
	fill(visited.begin(), visited.end(), false);

	//그래프 입력받기
	for (int i = 0; i < e; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		graph[u].push_back(make_pair(v, w));
	}

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

	cout << dijkstra(start, end) << endl;

	return 0;
}

int dijkstra(int start, int end)
{
	//방문할 노드(거리, 노드)
	priority_queue < edge, vector<edge>, greater<edge>> pq;

	//처음 시작점과 거리값 넣기
	pq.push(make_pair(0, start));
	mdistance[start] = 0;
	//다익스트라 계산
	while (!pq.empty())
	{
		//현재 위치노드 가져오기
		int cur_v = pq.top().second;
		pq.pop();
		//방문했다면 넘어가기
		if (visited[cur_v]) continue;

		visited[cur_v] = true;

		//현재 위치에서 연결된 노드 순회
		for (edge i : graph[cur_v])
		{
			int next_v = i.first;
			int next_e = i.second;

			//현재 거리보다 짧은 거리가 나오면 바꾸기
			if (mdistance[next_v] > mdistance[cur_v] + next_e)
			{
				mdistance[next_v] = mdistance[cur_v] + next_e;
				pq.push(make_pair(mdistance[next_v], next_v));
			}
		}
	}

	return mdistance[end];
}