급하게임개발

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

이 문제는 쉽다 일단 다익스트라 알고리즘을 사용하고 간선이 양방향이니 양방향으로 설정해 준다

다익스트라로 각지점의 최단거리를 구해준 후 거리를 정렬하여 범위 안에 있는 아이템에 개수를 더해준 누적값을 구해주면 된다

#include <iostream>
#include <vector>
#include <queue>
#include<algorithm>
#define INT_MAX 2147483647
using namespace std;
int NumOfItem[101];
vector<pair<int, int>> dijkstraV[101];
vector<int> distanceV(101);

void dijkstra(int start) {
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq; // 비용 노드
	pq.push(make_pair(0, start));
	distanceV[start] = 0;
	while (!pq.empty()) {
		int distanceOfTo = pq.top().first;
		int toVertex = pq.top().second;
		pq.pop();

		if (distanceOfTo > distanceV[toVertex]) {
			continue;
		}

		for (int i = 0; i < (int)dijkstraV[toVertex].size(); i++) {
			int cost = distanceOfTo + dijkstraV[toVertex][i].second;
			if (cost < distanceV[dijkstraV[toVertex][i].first]) {
				distanceV[dijkstraV[toVertex][i].first] = cost;
				pq.push(make_pair(cost, dijkstraV[toVertex][i].first));
			}
		}
	}
}

int getNumOfItem(int idx, int n, int m) {
	int sum=0;
	for (int i = 1; i <= n; i++) {
		if (distanceV[i] <= m) {
			sum += NumOfItem[i];
		}
	}
	return sum;
}


int main() {
	
	int n, m, r;
	int maxItem=0;
	cin >> n >> m >> r;
	for (int i = 1; i <= n; i++) {
		cin >> NumOfItem[i];
	}

	int from, to, cost;
	for (int i = 0; i < r; i++) {
		cin >> from >> to >> cost;
		dijkstraV[from].push_back({ to, cost });
		dijkstraV[to].push_back({ from,cost });
	}

	for (int i = 1; i <= n; i++) {
		distanceV.assign(101, INT_MAX);
		dijkstra(i);
		if(maxItem < getNumOfItem(i, n, m))
			maxItem = getNumOfItem(i, n, m);
	}
	cout << maxItem;
}

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

이 문제는 다익스트라 알고리즘을 그대로 사용하면 풀 수 있는 문제이다. 자세한 풀이 과정은 이전에 내가 올려놓은

https://fastgamedev.tistory.com/49

이 글의 문제와 똑같이 풀고나서 해당 도착지의 값만 출력해주는 문제라 매우 쉬웠다.

#include<iostream>
#include<queue>
#include<vector>
#define INT_MAX 2147483647
using namespace std;
vector<pair<int, int>> djikstraPQ [1001];
vector <int> distanceV(1001);
void dijkstra(int start) {
	priority_queue < pair<int, int>, vector < pair<int, int>>, greater<pair<int, int>>> pq;// front는 cost second 는 index
	pq.push({ 0, start });
	distanceV[start] = 0;
	
	while (!pq.empty()) {
		int costTo = pq.top().first;
		int toIdx = pq.top().second;
		pq.pop();

		if (distanceV[toIdx] < costTo) {
			continue;
		}

		for (int i = 0; i < (int)djikstraPQ[toIdx].size(); i++) {
			// 나랑 연결되어 있는애가 Second 비용이 front
			int cost = djikstraPQ[toIdx][i].second + costTo;
			if (cost < distanceV[djikstraPQ[toIdx][i].first]) {
				distanceV[djikstraPQ[toIdx][i].first] = cost;
				pq.push({ cost, djikstraPQ[toIdx][i].first });
			}
		}
	}
	
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, M, start, arrive;
	cin >> N >> M;
	int from, to, cost;
	for (int i = 0; i < M; i++) {
		cin >> from >> to >> cost;
		djikstraPQ[from].push_back({ to,cost });
	}
	cin >> start >> arrive;
	distanceV.assign(1001,INT_MAX);
	dijkstra(start);

	cout << distanceV[arrive];
}

이 문제의 경우 나에게 여러가지 에러를 보여줌으로 여러가지 함수를 사용할 때 주의 할점을 알려줬다. 일단  이 문제의 코드는 이렇게 된다

#include <iostream>
#include <queue>
#include <vector>
#define INT_MAX 2147483647
using namespace std;
vector<int> distanceV(20002); //시작점 부터 다른 정점까지의 거리를 저장
vector<bool> visited;
void djikstra(int start, vector<pair<int, int>> dijkstraGraph[]) {
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 거리, 노드 인덱스
	pq.push(make_pair(0, start));
	distanceV[start] = 0;

	while (!pq.empty()) {
		int distanceOfTo = pq.top().first;
		int toVertex = pq.top().second;
		pq.pop();

		if (distanceOfTo > distanceV[toVertex]) {
			continue;
		}

		for (int i = 0; i < (int)dijkstraGraph[toVertex].size(); i++) {
			int cost = distanceOfTo + dijkstraGraph[toVertex][i].second;
			int nextIndex = dijkstraGraph[toVertex][i].first;
			if (cost < distanceV[nextIndex]) {
				distanceV[nextIndex] = cost;
				pq.push(make_pair(cost, nextIndex));
			}

		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int vertex, edge, start;  //vertex는 정점 edge는 간선 start는 시작점을 입력 받는다.
	cin >> vertex >> edge >> start;
	vector<pair<int, int>> dijkstraGraph[20002];//다익스트라 알고리즘의 비용을 저장할 우선순위 큐
	for (int i = 1; i <= edge; i++) {
		int from, to, cost;  //from은 간선사이의 시작점,to는 도착점 , cost는 간선의 비용을 의미
		cin >> from >> to >> cost;
		dijkstraGraph[from].push_back(make_pair(to,cost));
	}
	distanceV.assign(20002, INT_MAX);
	djikstra(start, dijkstraGraph);
	for (int i = 1; i <= vertex; i++) {
		if (distanceV[i] == INT_MAX) {
			cout << "INF"<<endl;
		}
		else {
			cout << distanceV[i] << endl;
		}
	}
}

이 문제의 경우 일단 간선의 방향이 단 방향이다. 일단 이문제의 예시 input에 대한 과정의 그림을 첨부하겠다

이 그림 에서 원으로 되어 있는 그래프는 위에 dijkstra함수에 pq를 그린것이다. 밑에 배열은 distanceV를 그린것이다.

일단 처음 풀이에서

distanceV.assign(20002, INT_MAX);

이 코드를 통해 배열에 큰 값을 다 넣어주었다 이에 처음 벡터에는 INF값만 가득하다 그후 1,0 즉 시작점 1에서 도착지 1로가는 거리는 자기자신이므로 0을 넣어준다 그후 2,2순으로 pq순에서 팝되는 값과 나와 연결되어 있는 다음 인덱스의 값을 더해서 distanceV에 거리를 갱신해 준다. 즉 1이 팝되었을때는 2,3의 거릿값이 갱신된다. 이후 2가팝되었을 때는 3과 4에 연결되어있으므로 시작점부터 자기자신까지의 거리와 나랑 연결되어 있는 노드의 값을 더해서 만약 원래 그 노드까지의 거리보다 나를 통해 가는 거리가 짧으면 그 노드쪽의 값을 갱신해주고 아니면 넘어간다 이런식으로 계속 나까지의 거리와 다음 노드까지의 거리를 계속 갱신해주면서 최소 거리를 구하면 된다.

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/5639

이 문제의 경우 이진 검색 트리이긴 하지만 나는 굳이 따지자면 분할 정복이라고 봐도 될거 같다. 그 이유는 이문제의 경우

pivot을 기준으로 계속 나눠가면서 트리를 분리해서 출력을 해주어야 한다. 기존에 이진트리가 자신의 인덱스/2가 부모로 배열을 사용하는 것과 달리 특이하게 들어 왔다. 일단 이문제의 풀이는 아래 사진처럼 배열을 나누어야 했다.

#include <iostream>
using namespace std;

int arr[10005];

void post(int start, int end) {
	if (start >= end) return;
	//else if (start == end-1) {
	//	cout << arr[start] << endl;
	//	return;
	//}
	int i;
	for (i = start + 1; i < end; i++)
		if (arr[start] < arr[i]) 
			break;
	post(start + 1, i);
	post(i , end);
	cout << arr[start] << endl;
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int num;
	int idx=0;
	//while (true) {
	//	cin >> num;
	//	if (num == 0) {
	//		break;
	//	}
	//	else {
	//		arr[idx] = num;
	//		idx++;
	//	}
	//}
	while (cin >> num) {
		arr[idx] = num;
		idx++;
	}
	post(0, idx);
}

일단 이 문제는 입력 방식을

	while (cin >> num) {
		arr[idx] = num;
		idx++;
	}

이렇게 작성해 주어야 했는데 그이유는 이문제는 EOF를 통해 입력의 끝을 알기 때문에 우리가 프롬프트창에서 직접 사용자 입력을 해주게 되면 cin 의 기능이 끝나지 않는다 이에 나는 테스트 할때 main함수 부분의 주석을 해제해서 사용했다.

또한 이 문제의 경우 나의 post함수에 주석 부분은 성능을 올리기 위함이지만 가독성으로 볼때는 주석처리를 하는게 맞다.

그 이유는 위에 첨부한 풀이 그림을 보았을 때 원소가 2개남았을 때 무조건 start가 leaf단계이기 때문에 더이상 분할 할 필요가 없기 때문이다 하지만 맨끝에 원소가 하나 남았을 때는 굳이 출력을 해줄 필요가 없다. 이에 나는 원소가 하나 남았다는 것

if (start >= end) return;

을 이런식으로 start  인덱스와 end 인덱스가 같을 때 함수를 return 하여 더 이상 진행되지 않도록 하였다

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

이 문제는 중위순회 전위순회 후위순회를 직접 구현해보는 문제였다 문제자체는 그리 어렵지 않았다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <vector>
using namespace std;
int alpha = 65;
//26개의 원소를 0으로 초기화
struct node {
	char left;
	char right;
};
vector<node> v(26);
void preOrder(char node) {
	if (node == '.'-alpha)
		return;

	printf("%c", node + alpha);
	preOrder(v[node].left);
	preOrder(v[node].right);
}
void inOrder(char node) {
	if (node == '.'-alpha)
		return;

	inOrder(v[node].left);
	printf("%c", node + alpha);
	inOrder(v[node].right);
}
void postOrder(char node) {
	if (node == '.'-alpha)
		return;

	postOrder(v[node].left);
	postOrder(v[node].right);
	printf("%c", node + alpha);
}
int main() {
	int N;
	scanf("%d", &N);
	getchar();
	char parent, leftchild, rightchild;
	for (int i = 0; i < N; i++) {
		scanf("%c %c %c", &parent , &leftchild , &rightchild);
		getchar();
		v[parent-alpha].left = leftchild-alpha;
		v[parent-alpha].right = rightchild-alpha;
	}

	preOrder('A'-alpha);
	printf("\n");
	inOrder('A'-alpha);
	printf("\n");
	postOrder('A'-alpha);
	return 0;
}

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