급하게임개발

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

이 문제의 경우 반례를 생각 못해서 틀렸다 기존 코드에서 일반적인 반례는 잘 나왔으나 0 1을 입력했을 때  0 이 나와야 했는데 기존의 코드가 게속 1을 출력했다. 이 부분을 해결하니 해결되었다

#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;
int visited[100001];
int N, K;

int main() {
	cin >> N >> K;
	queue<int> hs;
	hs.push(N);
	memset(visited, -1, sizeof(visited));
	visited[N] = 0;
	while (true) {
		if (hs.front() == K) {
			break;
		}
		if (hs.front() <= 50000) {
			if (visited[hs.front() * 2] == -1) {
				hs.push(hs.front() * 2);
				visited[hs.front() * 2] = visited[hs.front()];
			}
			else {
				if (visited[hs.front() * 2] > visited[hs.front()]) {
					visited[hs.front() * 2] = visited[hs.front()];
					hs.push(hs.front() * 2);
				}
			}
		}
		if (hs.front() > 0) {
			if (visited[hs.front() - 1] == -1) {
				hs.push(hs.front() - 1);
				visited[hs.front() - 1] = visited[hs.front()] + 1;

			}
			else {
				if (visited[hs.front() - 1] > visited[hs.front()] + 1) {
					visited[hs.front() - 1] = visited[hs.front()] + 1;
					hs.push(hs.front() - 1);
				}
			}
		}
		if (hs.front() < 100000) {
			if (visited[hs.front() + 1] == -1) {
				hs.push(hs.front() + 1);
				visited[hs.front() + 1] = visited[hs.front()] + 1;
			}
			else {
				if (visited[hs.front() + 1] > visited[hs.front()] + 1) {
					visited[hs.front() + 1] = visited[hs.front()] + 1;
					hs.push(hs.front() + 1);
				}
			}
		}
		hs.pop();
	}
	cout << visited[K];
}

일단 이 문제의 경우 완전한 백트래킹이라기 보다 백트래킹과 BFS를 섞어서 해야 한다. 이에 나는 일단 BFS에서 주로 사용하는 큐를 작성하였다. 일단 이문제의 경우 BFS를 위해 그냥 계속 영역을 넓혀주면 된다 단 순서상으로 순간이동 즉 *2 부분을 먼저 해주었다. 그후 나머지 +1,-1 부분에서는 내가 접근하는 방식이 최소 방문횟수로 방문했으면 값을 넣어주고 아니면 무시하도록 작성하였다

이문제는 처음에 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이라는 변수에 넣고 이를 이용해서 앞으로 넣을 값이 중복되면 넣지 않도록 작성한다. 생각하기가 좀 까다로운 문제였던것 같다

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

이 문제는 일단 백준상에서 골드 5로 되어있는 문제다 근데 이문제를 보았을 때 느낀게 과연 내가 이 문제가  백트래킹인걸 모르고 풀었을 때 빠르게 정답을 유추 할 수 있었을까? 절대 아니다. 요즘 해당 알고리즘이 주어질 경우에는 그 알고리즘으로 문제를 빠르게 풀지만 내가 어떤 문젠지를 모르면 풀 수 있을 지는 모르겠다. 확실히 실무를 보다보니 머릿속에 생각한 것을 그대로 구현하는 구현능력은 조금 올라갔는데 앞으로도 계속 좋은 일이 있었으면 좋겠

#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
char arr[16];
char answer[16];
int cnta;
int cntj;
bool isPassword;
int solution(int level, int beforeindex) {
	if (level == N) {
		cnta = 0;
		cntj = 0;
		isPassword = false;
		for (int i = 0; i < N; i++) {
			if (answer[i] == 'a' || answer[i] == 'e' || answer[i] == 'i' || answer[i] == 'o' || answer[i] == 'u')
			{
				cnta++;
			}
			else
				cntj++;
			if (cnta > 0 && cntj > 1) {
				isPassword = true;
				break;
			}
		}
		if (isPassword) {
			for (int i = 0; i < N; i++) {
				cout << answer[i];
			}
			cout << endl;
		}
	}
	else {
		for (int i = beforeindex + 1; i <= M; i++) {
			answer[level] = arr[i];
			solution(level + 1, i);
		}
	}
	return 0;

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

}

이코드의 경우 모음의 개수를 세주는 CNTA 자음의 개수를 세주는 CNTJ라는 변수가 존재 한다 이 변수의 경우 루프를 돌다가 특정 조건을 만족했을 때 바로 루프를 탈출하게 해준다. 즉 최종 4글자 가 모였을 때 이 문자열이 모음이 1개이상 자음이 2개이상이면 더이상 조건을 판단할 필요없으니 루프를 탈출하게 해주는 것이다.

	else {
		for (int i = beforeindex + 1; i <= M; i++) {
			answer[level] = arr[i];
			solution(level + 1, i);
		}
	}

이 부분의 경우는 재귀를 이용해서 백트래킹을 하기 위함인데 정렬되어있는 arr값에서 자기 이전의 index보다 큰 인덱스 부터 시작하기에 무조건 오름차순이 된다.