TIL day 74

1. 코딩테스트

---

오늘은 class4에 "치킨 배달" 문제를 풀었습니다.

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

 

생각의 흐름

• 이 문제는 처음 보고 백트래킹이랑 bfs을 쓰는 문제인 줄 알았는데, 사실 N x N 의 borad는 크게 신경쓸 필요가 없었다.
• 치킨집이랑 집의 위치만 저장해두고 for문 돌면서 체크만 해주면 된다. (일단 N이 작으니까)
• 또한 N이 작기 때문에 모든 경우의 수를 백트래킹으로 그냥 골라버리면 된다.

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

int n;
int m;
vector<pair<int, int>> chicken;
vector<pair<int, int>> home;
vector<pair<int, int>> ans;
int isused[15];
int answer = INT_MAX;

void Check(vector<pair<int, int>>& ans)
{
	int temp = 0;
	for (int i = 0; i < home.size(); ++i)
	{
		int minDist = INT_MAX;
		for (const auto a : ans)
		{	
			minDist = min(abs(home[i].first - a.first) + abs(home[i].second - a.second), minDist);
		}
		temp += minDist;
	}
	answer = min(answer, temp);
}

void Choose(int cur, int start)
{
	if (cur == m)
	{
		Check(ans);
		return;
	}
	for (int i = start; i < chicken.size(); ++i)
	{
		if (!isused[i])
		{
			ans.push_back(chicken[i]);
			isused[i] = 1;
			Choose(cur + 1, i + 1);
			ans.pop_back();
			isused[i] = 0;
			
		}
	}
}

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

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			int num;
			cin >> num;

			if (num == 2)
				chicken.push_back({ i,j });
			if (num == 1)
				home.push_back({ i,j });
		}
	}

	for (int i = 0; i < m; ++i)
	{
		Choose(i, 0); //0->3 / 1->2 / 2->1
	}

	cout << answer;
}

공부할 점

• 내가 익숙하게 쓰는 방식의 경우 백트래킹 함수는 하나의 매개변수만을 가진다. 
  • 이 매개변수는 현재 몇개 선택했는지 알려주는 매개변수
• 그래서 백트래킹 문제에 오름차순이나 중복 제거 등의 조건이 걸리면, for문으로 뽑을 때 조건을 걸어주는 식으로 해왔다. (아래 코드 처럼)

for (int i = 0; i < c; ++i)
	{
		if (isused[board[i]] == 0)
		{
			if (answer.empty() || (!answer.empty() && (answer.back() < board[i])))
			{
				...
			}
		}
	}

• 그러나 다른 코드들도 참고하다 보니, 매개변수 두 개로 시작점을 지정하는 방식이 있어서 그 방식을 사용해보고 싶어서 해당 방식을 좀 더 공부해 보았다.
  
  

조합 관련 코드에 익숙해지면 좋을 것 같다. 

 

조합 관련 공부후, 몇가지 문제를 풀어 정리한 글

https://gbleem.tistory.com/150

백트래킹 2

 

 

2. 언리얼

---

추가적으로 데디케이티드 서버 공부를 진행하였습니다.

 

Role과 Replication에 대해 공부하였습니다.

 

Replication 에서는 OnRep_ 함수와 Frequency에 대한 내용을 중심으로 공부하였습니다.

공부한 내용은 아래 글에 추가로 작성하였습니다.

https://gbleem.tistory.com/148

Unreal Engine - 데디케이티드 서버 2