급하게임개발

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

이 문제는 솔직히 설명이 겁나 불친절하다 

정확히 이문제는 핵심이 나를 기준으로 나보다 크기가 작고 같은 거리에 있는 물고기 들은 위에에서 왼쪽부터 오른쪽 까지 검사하고 내려와서 왼쪽부터 오른쪽 까지 검사하면서 이 순으로 탐색을 하는 거였다.
단 위에를 듣고 BFS  이동방향을 1,0 ->0,-1 ->0,1 ->-1,0 이렇게 만 하면 안풀린다

while (!bfsQ.empty()) {
		
				otherX = bfsQ.front().second.first;
				otherY = bfsQ.front().second.second;
				otherCost = bfsQ.front().first;
				if (CanEat(otherX, otherY) && otherCost<=cost) {
					if (otherX < startX) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
					else if (otherX == startX && startY>otherY ) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
				}

핵심은 이부분이다 내가 물고기를 먹을 수있는 지역으로 갔을 때 현재 큐에  들어와 있는 것중 나보다 거리가 작거나 같고 행의 값이  위에 있거나 혹은 행이 같다면 열값이 더 먼저인 애를 찾아서 거기를 가야한다 이에 의해 필자는 행을 검사에서 위에있으면 해당 행으로 탐색지점을 바꿔줬고 같다면 열값이 더 작은 쪽으로 옮겨줬다

#include <iostream>
#include <queue>
using namespace std;
int n;
int arr[20][20] = { 0, };
bool isVisited[20][20];
int fishSize = 2;
int eatFish = 0;
int cnt = 0;
queue<pair<int,pair<int, int>>>  bfsQ;

bool CanEat(int x, int y) {
	if (arr[x][y]>0&&arr[x][y] < fishSize) {
		return true;
	}
	return false;
}
bool canGo(int x, int y) {
	if (x >= 0 && x < n && y >= 0 && y < n && !isVisited[x][y] && (CanEat(x, y) || arr[x][y] == 0 || arr[x][y]==fishSize))
		return true;
	else
		return false;
}

void Bfs(int x, int y) {
	bfsQ.push({ cnt,{x,y} });
	arr[x][y] = 0;
	int startX, startY, cost;
	int otherX, otherY, otherCost;
	while (!bfsQ.empty()) {
		startX = bfsQ.front().second.first;
		startY = bfsQ.front().second.second;
		cost = bfsQ.front().first;
		bfsQ.pop();
		if (CanEat(startX, startY)) {
			cnt += cost;
			while (!bfsQ.empty()) {
		
				otherX = bfsQ.front().second.first;
				otherY = bfsQ.front().second.second;
				otherCost = bfsQ.front().first;
				if (CanEat(otherX, otherY) && otherCost<=cost) {
					if (otherX < startX) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
					else if (otherX == startX && startY>otherY ) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
				}

				bfsQ.pop();
				
			}
			bfsQ.push({ 0, {startX, startY}});
			eatFish += 1;
			if (eatFish == fishSize) {
				fishSize += 1;
				eatFish = 0;
			}
			arr[startX][startY] = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					isVisited[i][j] = false;
				}
			}
			isVisited[startX][startY] = true;
			cost = 0;
		}

		if (canGo(startX-1,startY)) {
			bfsQ.push({ cost + 1,{startX -1,startY}});
			isVisited[startX - 1][startY] = 1;
		}
		if (canGo(startX, startY-1)) {
			bfsQ.push({ cost + 1,{startX ,startY - 1} });
			isVisited[startX][startY-1] = 1;
		}
		if (canGo(startX , startY+1)) {
			bfsQ.push({ cost + 1,{startX ,startY + 1} });
			isVisited[startX][startY + 1] = 1;
		}
		if (canGo(startX+1 , startY)) {
			bfsQ.push({ cost + 1,{startX + 1,startY} });
			isVisited[startX + 1][startY] = 1;
		}
	}

}
int main() {
	cin >> n;
	int startIdxCol, startIdxRow;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9) {
				startIdxCol = i;
				startIdxRow = j;
			}
		}
	}

	Bfs(startIdxCol, startIdxRow);
	cout << cnt;
}

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

이번 문제도 그래프를 이용해 최소 신장 트리를 만드는 문제이다 단 저번 게시물에는 크루스칼 알고리즘을 이용 하였으나 이번 알고리즘은 프림 알고리즘을 이용해서 풀었다.

프림 알고리즘은 현재 나와 연결된 노드들을 점점확장하면서 최소 신장 트리를 만드는 것이다
프림 알고리즘은 크루스칼알고리즘과 다르게 간선들이 많을 때 효율적이다.

프림알고리즘의 로직은 대충 일단 내가 갈수 있는 곳중 가까운 곳을 연결한다. 그리고 내가 갈수 있는 곳과 그 갈수 있는 버텍스를 통해서 갈수 있는 곳중 가장 비용이 낮은 곳으로 간다

위의 과정을 vertex의 갯수-1 만큼 반복해주면 된다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int parent[1001];
vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>> inputData(1001);
int findParent(int x) {
	if (parent[x] == x)
		return x;
	else return parent[x] = findParent(parent[x]);
}
bool isSameParent(int x, int y) {
	int parentOfX = findParent(x);
	int parentOfY = findParent(y);
	if (parentOfX == parentOfY) {
		return true;
	}
	else {
		return false;
	}
}

void uni(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	parent[y] = x;
}
int main() {
	int n, m;
	cin >> n;
	cin >> m;
	int com1 = 0, com2 = 0, cost = 0,result=0;
	for (int i = 0; i < m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		inputData[from].push({ cost,to });
		inputData[to].push({ cost,from });
	}
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}
	for (int i = 1; i < n ; i++) {
		while (!inputData[1].empty()) {
			com1 = 1;
			com2 = inputData[1].top().second;
			cost = inputData[1].top().first;
			inputData[1].pop();
			if (!isSameParent(com1, com2)) {
				result += cost;
				uni(com1, com2);
				while (!inputData[com2].empty()) {
					inputData[com1].push(inputData[com2].top());
					inputData[com2].pop();
				}
				break;
			}
		}
	}
	cout << result;
}

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

이 문제의 경우 최소 신장트리를 만들어 내는 문제이다 모든 정점들을 이었을 때 각 간선들의 최소가 되는 트리를 최소 신장트리라고 한다  이문제의 경우 내가 트리의 크루스칼 알고리즘을 이용해서 풀었다

크루스칼 알고리즘은 
1. 각 경로들의 cost 값으로 오름차순 정렬 한다
2. 각 경로들의 vertex 간 비교해서 각 vertex들이 이어진 경로의 root와 비교해서 서로 다르면 잇고 아니면 연결하지 않는다
3. 2의 과정을 반복한 후 Cost의 값을  도출한다

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 가중치 start end순
vector<pair<int, pair<int, int>>> inputData;
int parent[10001] = { 0, };

int findParent(int x) {
	if (parent[x] == x)
		return x;
	else return parent[x] = findParent(parent[x]);
}

bool sameParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	if (x == y)
		return true;
	else
		return false;
}
void uni(int  x, int y) {
	x = findParent(x);
	y = findParent(y);
	parent[y] = x;
}
int main() {
	int  v, e,cost;
	cost = 0;
	cin >> v >> e;
	int tmp1, tmp2, tmp3;
	for (int i = 0; i < e; i++) {
		cin >> tmp1 >> tmp2 >> tmp3;
		inputData.push_back({ tmp3,{tmp1,tmp2} });
	}

	sort(inputData.begin(), inputData.end());
	for (int i = 1; i <= v; i++) {
		parent[i] = i;
	}

	for (int i = 0; i<inputData.size(); i++) {
		if (!sameParent(inputData[i].second.first, inputData[i].second.second)) {
			uni(inputData[i].second.first, inputData[i].second.second);
			cost += inputData[i].first;
		}
	}
	cout << cost;
}

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

이 문제의 경우 흐름대로 생각하면 그게 정답이다 단 주의 할점은 단지 하나의 priority queue로 만한다면 음수부분의 처리가 이상하게 될것이다 이에 나는 음수와 0을 저장하는 priority queue와 양수만을 저장해주는 priority queue로 작성하였으며 음수 와 0을 묶은 이유는 음수와 음수의  곱은 양수이고 만약 음수와 0만 큐에 남았을 때는 2개를 곱하여 0을 반환함으로 작은 값을 반환할거라고 생각했다

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
	priority_queue<int> plusNum;
	priority_queue<int,vector<int>, greater<int>> negativeNum;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int temp1;
		cin >> temp1;
		if (temp1 > 0) {
			plusNum.push(temp1);
		}
		else {
			negativeNum.push(temp1);
		}
	}
	int sum = 0;
	while (!plusNum.empty())
	{
		int num1, num2;
		num1 = plusNum.top();
		plusNum.pop();
		if (plusNum.empty()) {
			sum += num1;
			break;
		}
		num2 = plusNum.top();
		plusNum.pop();

		if (num1 != 1 && num2 != 1) {
			sum += num1 * num2;
		}
		else {
			sum += num1 + num2;
		}
	}
	while (!negativeNum.empty())
	{
		int num1, num2;
		num1 = negativeNum.top();
		negativeNum.pop();
		if (negativeNum.empty()) {
			sum += num1;
			break;
		}
		num2 = negativeNum.top();
		negativeNum.pop();
		sum += num1 * num2;

	}

	cout << sum;

}

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

이 문제의 경우 Priority Queue를 사용하지 않으면 시간 초과 가 발생한다 이문제의 핵심은 작은 가방에 담을수 있는 가장 큰걸 담고 그다음크기의 가방에 그 가방의 크기에  담을 수 있는것중 가장 큰것을 담으면 된다.  
이 로직을 구현하기 위해서는 일차적으로 가장 작은 무게에 담을 수 있는 모든 물건들을 선택한다 거기서 가장 큰 애를 선택한다. 이차적으로 이전에 담고 남은 물건들중에 두번째 무게에 담을 수 있는 모든 물건들을 모두 고른 후 이전 애 고른애들과 합쳐서 놓은 다음 그중에 큰거를 고르면 된다.

이 로직에서 일단 필요한건 우선순위 큐다. 일차적으로 가방을 작은 순으로 나열해서 가장 작은 가방에 담을 수  있는 애를 우선순위큐에 담는다 보석들도 무게순으로 정렬 되어 있다 그래서 첫번째 가방에 담으면 첫번째 가방에 담긴 마지막 인덱스 이후로 무게가 큰 보석들이 남는다 그중 두번째 가방에 닿을 수 있는 물건들을 담아서 우선순위 큐에 넣는다. 거기서 최고 큰값을 선택 한다

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

using namespace std;

priority_queue<int> pq;
int bag[300000];
pair<int, int> jewerly[300000];

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

	for (int i = 0; i < n; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;
		jewerly[i] = { temp1,temp2 };
	}

	for (int i = 0; i < k; i++) {
		cin >> bag[i];
	}

	sort(jewerly, jewerly + n);
	sort(bag, bag + k);

	int idx=0;
	long long sum = 0;

	for (int i = 0; i < k; i++) {
		while (idx < n && bag[i] >= jewerly[idx].first) {
			pq.push(jewerly[idx].second);
			idx++;
		}
		if (!pq.empty()) {
			sum += pq.top();
			pq.pop();
		}
	}
	cout << sum;
}

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

이 문제는 투포인터 문제이다 또한 에라토스테네스의 체로 소수를  걸러내야한다. 이후  투포인터로 연속된 소수의 합을 구하면 된다 

예시로 우리 15라는 숫자를 연속 된 소수로 만들자고 가정하자
15밑의 소수는

이렇게 존재 한다 우리가 연속 된 소수의 합을 만들기 위해서는 Start부분과 End부분이 있으면 된다

star부터 end까지의 합이 우리가 구하려는 숫자보다 작을 때 end의 index를 1증가 시켜주고 아니면 start의 인덱스를 증가시킨다 구하려는 값과 같으면 해당 구간에서는 이미 구해진 것이므로 start의 인덱스 와 end인덱스를 1증가시켜준다

이런느낌으로 구간을 바꿔가면서 계산 해주면 된다

#include <iostream>
#include <vector>
using namespace std;
vector<int> primeNumbers;
vector<int> check;

//n 이하의 정수에 대한 소수를 에라토스테네스의 체로  걸러냄
void getPrimeNumbers(int n) {
	for (int i = 2; i <= n; i++) {
		if (check[i])
			continue;
		else {
			primeNumbers.push_back(i);
			for (int j = i; j <= n; j += i) {
				check[j] = 1;
			}
		}
	}
}
int main() {
	int n,start,end,cnt;
	cin >> n;
	check.resize(n + 1, 0);
	getPrimeNumbers(n);
	start = primeNumbers[0];
	end = primeNumbers[0];
	int startidx = 0;
	int endidx = 0;
	cnt = 0;
	while (startidx <= endidx && endidx<primeNumbers.size()) {
		int sum = 0;
		for (int i = startidx; i <= endidx; i++) {
			sum += primeNumbers[i];
		}
		if (sum == n) {
			cnt += 1;
			startidx += 1;
			endidx += 1;
		}
		else  if (sum < n) {
			endidx += 1;
		}
		else {
			startidx += 1;
		}	
	}
	cout << cnt;
}

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

이 문제의 경우 다르게보면 조합이지만 이 문제의 분류가 비스마스킹으로 되어 있어서 비스마스킹으로 풀려구 생각했다
이 문제의 비트마스킹은 총 나는 2개를 사용 했는데 일단 team의 점수를 저장하는데 사용 했다 (이 부분에서 좀더  최적화가 가능하나 귀찮아서 진행 하지않았다) 두번째로는 팀들을  나누는데 비트마스킹을 사용했다.

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			int teamNum = (1 << i) | (1 << j);
			teamP[teamNum] = arr[i][j]+arr[j][i];
		}
	}

나는 일단 teamP라는 곳에 두명이 차지했을 때의 점수를 넣어줬다 위에처럼 1001일때는 5임으로 4번과 1번팀이 같이 되어있을 때를 나타내며 각팀이 만들어내는 숫자에 따라 점수를 넣어줬다

숫자 일단 이문제의 경우 이렇게 1번팀 0번팀으로 나눌수 있는데 숫자 5의 경우 팀을 위에 그림처럼 나누게 된다

for (int i = 1; i < (1<<n); i++) {
	for (int j = 0; j <= n; j++) {
		if (i & (1 << j))
			team1.push_back(j);
		else
			team2.push_back(j);
	}

이 부분의로직은 이렇게 되는데 i=1부터 시작한다 그  이유는 0번비트만 있을 때는 팀을 만들 수 없으므로 0번 비트  1번 비트 2개가 있는 상황 부터 시작하기 위해서 1번 부터 비트를 사용한다 또한 1<<n 을한 이유는 우리의 테스트 케이스 4를 예시로 들면 비트 4개로 만들수 있는 최댓값은 15인데 1<<4는 16이므로 이부분보다 작을 동안만 우리는 연산을 해주면된다

j변수를 사용하는 루프의 경우는 이제 각비트가 어떤 비트인지 판별하기 위해서 해당 연산을 진행하고 0인지 1인지에 따라 팀에 분배해주게 된다

그후 우리는 두명만이 각 짝을 이뤄 점수가 있으므로

		for (int k = 0; k < team1.size(); k++) {
			for (int p = k + 1; p < team1.size(); p++) {
				sum1 += teamP[(1 << team1[k]) | (1 << team1[p])];
			}
		}
		for (int k = 0; k < team2.size(); k++) {
			for (int p = k + 1; p < team2.size(); p++) {
				sum2 += teamP[(1 << team2[k]) | (1 << team2[p])];
			}
		}

이런 식으로 각 팀의 연산을 해준다

전체 코드는 아래와 같다

#include <iostream>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
int arr[20][20];
vector<int> team1;
vector<int> team2;
int maxresult = 1e9;
int teamP[2097152];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			int teamNum = (1 << i) | (1 << j);
			teamP[teamNum] = arr[i][j]+arr[j][i];
		}
	}
	int sum1 = 0;
	int sum2 = 0;
	
	for (int i = 1; i < (1<<n); i++) {
		for (int j = 0; j <= n; j++) {
			if (i & (1 << j))
				team1.push_back(j);
			else
				team2.push_back(j);
		}
		for (int k = 0; k < team1.size(); k++) {
			for (int p = k + 1; p < team1.size(); p++) {
				sum1 += teamP[(1 << team1[k]) | (1 << team1[p])];
			}
		}
		for (int k = 0; k < team2.size(); k++) {
			for (int p = k + 1; p < team2.size(); p++) {
				sum2 += teamP[(1 << team2[k]) | (1 << team2[p])];
			}
		}
		if (team1.size() && team2.size())
			maxresult = min(maxresult, abs(sum1 - sum2));
		team1.clear();
		team2.clear();
		sum1 = 0;
		sum2=0;
	}

	cout << maxresult;
}

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

이 문제는 다익스트라 알고리즘을 사용해서 풀 수 있다 현재 이블로그에 있는 다익스트라 알고리즘에 관한 문제는 비슷한 양상을 보인다

void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ startNode,toCost });

	while (!djikstra_pq.empty()) {
		int toVertex = djikstra_pq.top().first;
		int toCost = djikstra_pq.top().second;

		djikstra_pq.pop();

		int distanceToNextVertex = distanceV[toVertex];
		if (distanceToNextVertex < toCost) {
			continue;
		}
		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			// 다음 인덱스로 가는 cost
			int cost = edgeList[toVertex][i].second + toCost;
			// 나를 통해 갈 다음 IDX
			int nextIdx = edgeList[toVertex][i].first;
			if (cost < distanceV[nextIdx]) {
				distanceV[nextIdx] = cost;
				djikstra_pq.push({ nextIdx,cost });
			}
		}


	}
}

이 부분이 핵심 부분인데

1. 일단 start 즉 시작점으로 부터의 거리를 구할 것이기에 Start -> Start의 toCost를 0 start->start의 다음인덱스 start를 우선순위 큐에 넣는다 (우선순위 큐는 값이 작은게 root 에 있다)

2.그리고 우선순위 큐가 빌때 까지 
현재 우선순위 큐에 들어가 있는 버텍스와 경로들을 뽑아서 해당 경로들에  영향을 받는 다른 vertex들의 cost값을 업데이트 해줘야 한다

3.일단 node1 -> node2 로 갈때의  현재 우선순위 큐에들어가 있는 가장 작은 애를 가져온다 그후 내가 node1을 통해서 가는 node2 까지의 거리와 이전부터 업데이트  해놓은 1부터 node2까지의 거리를 비교해서 작은 값일 때  node2를 통해서 가는 거리들의 값을 업데이트 해준다 그후 다음 업데이트를 할수도 있으니 해당 값들을 우선순위 큐에 넣어주고 반복한다

전체 코드는 아래와 같다

#include <iostream>
#include<queue>
using namespace std;
int n, m;

#define INF 1e9+7
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> djikstra_pq;
vector<pair<int, int>> edgeList[5001];
vector<int> distanceV(5001);
void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ startNode,toCost });

	while (!djikstra_pq.empty()) {
		int toVertex = djikstra_pq.top().first;
		int toCost = djikstra_pq.top().second;

		djikstra_pq.pop();

		int distanceToNextVertex = distanceV[toVertex];
		if (distanceToNextVertex < toCost) {
			continue;
		}
		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			// 다음 인덱스로 가는 cost
			int cost = edgeList[toVertex][i].second + toCost;
			// 나를 통해 갈 다음 IDX
			int nextIdx = edgeList[toVertex][i].first;
			if (cost < distanceV[nextIdx]) {
				distanceV[nextIdx] = cost;
				djikstra_pq.push({ nextIdx,cost });
			}
		}


	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int temp1, temp2, temp3;
		cin >> temp1 >> temp2 >> temp3;

		edgeList[temp1].push_back({ temp2,temp3 });
		edgeList[temp2].push_back({ temp1,temp3 });

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

	distanceV.assign(n + 1, INF);
	djikstraSolution(start);

	cout << distanceV[end];
}