급하게임개발

이문제는 처음에 bfs로 접근 했다 bfs로 풀었을 때는 각 지점에서 bfs로 확장해나가다가 치킨집이 모든 집을 방문했을 때의 각치킨집의 거리합을 이용해서 최솟값을 도출했으나 시간초과가 발생하였다. 의외로 이 문제는 간단하게 풀리는 문제 였다 그냥 치킨집에서 N개를 뽑아서 얘네들을 집과의 거리를 구해서 집과 치킨의 최소 거리를 저장해준 후 이를 계속 비교해가며 최솟값을 찾는 문제였다. 백트랙킹을 이용한 조합을 사용하여 풀었다.

#include <iostream>
#include <vector>
#include <utility>
#define MAX_INT 2147483647
using namespace std;
int N, M;
vector<pair<int, int>> chickenPos;
bool isVisited[50] = { 0, };
vector<pair<int, int>> housePos;
vector<pair<int, int>> selectedChicken;
int minCityDistance=MAX_INT;
void calculateDistance() {
	int distanceOfCity = 0;
	for (int i = 0; i < housePos.size(); i++) {
		int minDistance = MAX_INT;
		for (int j = 0; j < selectedChicken.size(); j++) {
			int distance = abs(housePos[i].first - selectedChicken[j].first) + abs(housePos[i].second - selectedChicken[j].second);
			if (distance < minDistance) {
				minDistance = distance;
			}
		}
		distanceOfCity += minDistance;
	}
	if (distanceOfCity < minCityDistance) {
		minCityDistance = distanceOfCity;
	}
}
void selectChicken(int idx, int level) {
	if (level == M) {
		calculateDistance();
		return;
	}
	for (int i = idx; i < chickenPos.size(); i++) {
		if (!isVisited[i]) {
			isVisited[i] = true;
			selectedChicken.push_back(chickenPos[i]);
			selectChicken(i , level + 1);
			isVisited[i] = false;
			selectedChicken.pop_back();
		}
	}
}
int main() {
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	int tmp;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> tmp;
			if (tmp == 2) {
				chickenPos.push_back(make_pair(i, j));
			}
			else if (tmp == 1) {
				housePos.push_back(make_pair(i, j));
			}
		}
	}
	selectChicken(0,0);
	cout << minCityDistance;
}

일단 이 코드의 이 부분 부터 보자

void selectChicken(int idx, int level) {
	if (level == M) {
		calculateDistance();
		return;
	}
	for (int i = idx; i < chickenPos.size(); i++) {
		if (!isVisited[i]) {
			isVisited[i] = true;
			selectedChicken.push_back(chickenPos[i]);
			selectChicken(i , level + 1);
			isVisited[i] = false;
			selectedChicken.pop_back();
		}
	}
}

이 부분은 일단 치킨집의 좌표들이 저장되어있는 chickenPos vectory 에서 치킨을 선택한 후 에 selectedChicken 에 넣어준다 그후 isVisited를 true로 설정해 주어 방문했다고 한 뒤 다쓰고 나면 false로 바꿔주고 selectedchicken 벡터에서 제거해 준다. 그후 level이 M 즉 M개의 치킨집을 뽑았으면 calculate distance 함수를 실행한다.

void calculateDistance() {
	int distanceOfCity = 0;
	for (int i = 0; i < housePos.size(); i++) {
		int minDistance = MAX_INT;
		for (int j = 0; j < selectedChicken.size(); j++) {
			int distance = abs(housePos[i].first - selectedChicken[j].first) + abs(housePos[i].second - selectedChicken[j].second);
			if (distance < minDistance) {
				minDistance = distance;
			}
		}
		distanceOfCity += minDistance;
	}
	if (distanceOfCity < minCityDistance) {
		minCityDistance = distanceOfCity;
	}
}

이 함수의 로직도 매우 간단하다 아까 이전 함수에서 뽑은 치킨집들이랑 각 집과 의 거리를 구하고 각집마다 치킨집에서 가장 가까운 거리를 minDistance에 저장한다 그후 각집의 치킨집까지의 최솟값을 더한후 이전에 뽑았던 최솟값과 비교를 해서 작은애를 다시 넣어준다.

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

이 문제는 N과 M 문제 중에 어려운 쪽에 속했다 이에 풀기 위해서는 기본적인 백트래킹 알고리즘을 사용하데 조건을 잘 맞춰주어야했다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
int beforearr[8] = { 0, };
int arr[8];
int answer[8];
bool isused[8];
int cnt;
void solution(int level) {
	if (level == M) {
		for (int i = 0; i < M; i++) {
			cout << answer[i] << " ";
		}
		cout << endl;
		return;
	}
	int finalusing = 0;
	for (int i = 0; i < N; i++) {
		if (!isused[i] && finalusing!=arr[i] ){
			answer[level] = arr[i];
			finalusing = answer[level];
			isused[i] = true;
			solution(level + 1);
			isused[i] = false;
		}
	}

}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N);
	solution(0);

}

이 문제를 해결하는 방법이다 이 문제의 경우 백트래킹을 사용하기 위해 일단 입력받은 배열을 오름차순으로 정렬을 해주면 같은 level내에서 같은 값을 뽑아서 사용하게 되면 똑같은 수열이 나오기에 스택에서 바로 이전에 썼던 값만 안써주면 중복을 피할 수 있다 예를 들어 1 7 9 9 로 나열되어 있으면 1번째 9가 사용되면 2번째 9는 사용되지 않기 위함이다 1번째 9를 사용할때는 이전에는 7을 사용했으므로 사용할 수 있지만 2번째 9의 경우 1번째 9를 이전에 사용했으므로 사용할 수 없다 즉 바로 이전에 사용한 값을 final using이라는 변수에 넣고 이를 이용해서 앞으로 넣을 값이 중복되면 넣지 않도록 작성한다. 생각하기가 좀 까다로운 문제였던것 같다

이번에 모회사 코테를 보는 데 내가 못풀었던 문제에서 중복순열을 2번사용하여 경우의 수를 구하는 브루트포스 방식의 문제가 출제 되었던 거 같다. 내가 생각한게 정답이 아닐 수 도 있지만 적어도 내가 생각한데로 풀기 위해서는 중복순열과 순열을 구현했어야 했다. 하지만 오랫동안 기본적인 알고리즘 조차 손을 놓았어서. 역시 급하게 준비한 코테답게 불합격 메일을 기다리고 있다. 확실히 불합격이 되더라도 코테를 직접 보면서 어떤 식으로 공부해야할지 감이 잡히기 시작했다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//중복 순열
int caseNum;
int arr[100000];
bool vectorIndexUsed[100000];
void DuplicatePermutation(int level, vector<int> caseVector) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < caseVector.size(); i++) {
		arr[level] = caseVector[i];
		DuplicatePermutation(level + 1, caseVector);
	}
}


void Permutation(int level, vector<int> caseVector) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < caseVector.size(); i++) {
		if (!vectorIndexUsed[i]) {
			vectorIndexUsed[i] = true;
			arr[level] = caseVector[i];
			Permutation(level + 1, caseVector);
			vectorIndexUsed[i] = false;
		}
	}
}

void Combination(int level, vector<int> caseVector, int beforeIndex) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = beforeIndex; i < caseVector.size(); i++) {
		arr[level] = caseVector[i];
		Combination(level + 1, caseVector, beforeIndex + 1);
	}
}

int main() {
	cin >> caseNum;
	vector<int> dupPermuTest = { 1,4,5,2 };
	DuplicatePermutation(0, dupPermuTest);
	cout << "====================================="<<endl;
	Permutation(0, dupPermuTest);
	cout << "====================================="<<endl;
	sort(dupPermuTest.begin(), dupPermuTest.end());
	Combination(0, dupPermuTest, 0);
}

일단 기억나는 것은 주어진 벡터에서 몇명을 뽑아야하는 것이었다 이에 나는 중복순열,순열,조합순으로 현재 구현했다.

void DuplicatePermutation(int level, vector<int> caseVector) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < caseVector.size(); i++) {
		arr[level] = caseVector[i];
		DuplicatePermutation(level + 1, caseVector);
	}
}

중복 순열의 경우 똑같은 걸 여러번 사용해도 되니 굳이 사용했는지 안했는 지 체크할 필요가 없다

void Permutation(int level, vector<int> caseVector) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < caseVector.size(); i++) {
		if (!vectorIndexUsed[i]) {
			vectorIndexUsed[i] = true;
			arr[level] = caseVector[i];
			Permutation(level + 1, caseVector);
			vectorIndexUsed[i] = false;
		}
	}
}

순열의 경우 vector에서 순서가 다르면 다른것으로 인정하고 중복은 허하지 않는다

void Permutation(int level, vector<int> caseVector) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < caseVector.size(); i++) {
		if (!vectorIndexUsed[i]) {
			vectorIndexUsed[i] = true;
			arr[level] = caseVector[i];
			Permutation(level + 1, caseVector);
			vectorIndexUsed[i] = false;
		}
	}
}

조합은 중복을 허하지도 않고 순서가 달라도 같은 수를 뽑았으면  허용치 않는다.

void duplicateCombination(int level, vector<int> caseVector, int beforeIndex) {
	if (level == caseNum) {
		for (int i = 0; i < caseNum; i++) {
			cout << arr[i];
		}
		cout << endl;
		return;
	}
	for (int i = beforeIndex; i < caseVector.size(); i++) {
		arr[level] = caseVector[i];
		duplicateCombination(level + 1, caseVector, i);
	}
}

중복 조합은 같은 수를 뽑을 수 있고 순서가 존재한다 이에 같은수는 뽑을 수 있지만 순서가 다르고 동일한 요소로 이루어져있는 것은 이전에 뽑은것과 같음으로 허용치 않는다

이 정도 문법은 꼭 기억하도록 하자