급하게임개발

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

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> djikstra_pq;
vector<int> distanceV(50001);
vector<pair<int, int>> cowData[50001];
int n, m;
void djikstra(int start) {
	djikstra_pq.push({ 0,start });
	distanceV[start] = 0;

	while (!djikstra_pq.empty()) {
		int costTo = djikstra_pq.top().first;
		int toIdx = djikstra_pq.top().second;
		djikstra_pq.pop();

		if (distanceV[toIdx] < costTo)
			continue;
		for (int i = 0; i < cowData[toIdx].size(); i++) {
			int nextCost = cowData[toIdx][i].first;
			int nextVertex = cowData[toIdx][i].second;
			if (distanceV[nextVertex] > nextCost + costTo) {
				distanceV[nextVertex] = nextCost + costTo;
				djikstra_pq.push({nextCost+costTo,nextVertex});
			}
		}
	}
}
int main() {
	cin >> n >> m;
	int from, to, cost;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> cost;
		cowData[from].push_back({ cost,to });
		cowData[to].push_back({ cost,from });
	}
	distanceV.assign(50001, INF);
	djikstra(1);
	cout << distanceV[n];
}

그냥 이문제는 다익스트라 문제이다 다익스트라를 많이 풀어보신 분이라면 쉽게 풀 수 있었을 것이다

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

이 문제는 처음에 dfs로 만 풀었으나 시간초과 가 났다 이에 dp와 섞어서 풀어야 한다는 힌트를 보게 되었다

			dp[x][y] = dp[x][y] + dfs(x + xidx[i],y + yidx[i]);

dp의 점화식은 이와 같은데 그이유는 나는 내가 다음에 갈수 있는 경로들이 갈수 있는 경로들의 합으로 표현할수 있기 때문이다

나는 dp배열을 -1로초기화를 해주었는데 그이유는 방문하지 않았다는 표시를 -1로 하게되었습니다 0은 방문은 했으나 해당 영역을 통해서 경로를 찾을 수 없는 것이라고 결정 하였습니다. 경로를 탐색하러 들어갔을 때 이미 해당 노드를 방문 한적이 있으면 해당 노드를 통해서 방문했던 길의 갯수가 해당 노드의 저장이 되어있기에 해당 노드의 값을 그대로 반환해주었습니다.

#include <iostream>
#include <set>
using namespace std;
int arr[500][500];
int dp[500][500];
int m, n;
int cnt;
int xidx[4] = { 1,0,-1,0 };
int yidx[4] = { 0,1,0,-1 };
bool canGo(int x, int y, int height) {
	if (x >= 0 && x < m && y>=0 && y < n && height > arr[x][y])
		return true;
	else
		return false;
}

int dfs(int x,int y) {
	if (x == m - 1 && y == n - 1) {
		return 1;
	}
	if (dp[x][y] != -1)
	{
		return dp[x][y];
	}

	dp[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		if (canGo(x + xidx[i], y + yidx[i], arr[x][y])) {
			dp[x][y] = dp[x][y] + dfs(x + xidx[i],y + yidx[i]);
		}
	}
	return dp[x][y];
}
int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}
	}
	cout << dfs(0, 0);
}

전체 로직은 위와 같다

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

이 문제는 최소 신장트리 문제이다 이문제의  경우 일부러 프림 알고리즘을 사용해서 풀었다. 프림 알고리즘의 경우 트리들을 계속 이어붙여나가면서 갈수 있는 곳중 최소의 버텍스를 선택해서 계속 트리를 확장해 가는 코드이다. 이전에 게시물에 프림알고리즘에 대해 설명한게 있다. 이문제의 경우는 좌표로 주어지기 때문에 좌표에 인덱스를 부여해주고 거리를 cost로 해서 프림알고리즘을 풀어주면 되는 문제였다

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>

using namespace std;

vector<priority_queue < pair<float, int>, vector<pair<float, int>>, greater<pair<float, int>>>> inputData(101);
int parent[101];
vector<pair<float, float>> stars(101);
float starDistance;
float makeFloat(float x) {
	return round(100 * x) / 100;
}

float getDistance(float x1, float y1, float x2, float y2) {
	return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

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

void uni(int x, int y) {
	x = findParent(x);
	y = findParent(y);

	parent[y] = x;
}

bool isSameParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);

	if (x == y)
		return true;
	else
		return false;

}
int main() {
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		float tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		stars[i] = { tmp1,tmp2 };
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			float distance = getDistance(stars[i].first, stars[i].second, stars[j].first, stars[j].second);
			if (i == j)
				continue;
			inputData[i].push({ distance, j });

			
		}
		parent[i] = i;
	}

	for (int i = 1; i <= n; i++) {
		int star1 = 1;
		while (!inputData[1].empty()) {
			int star2 = inputData[1].top().second;
			float cost = inputData[1].top().first;
			inputData[1].pop();

			if (!isSameParent(star1, star2)) {
				starDistance += cost;
				uni(star1, star2);
				while (!inputData[star2].empty()) {
					inputData[1].push({ inputData[star2].top().first, inputData[star2].top().second });
					inputData[star2].pop();
				}
				break;
			}
		}
	}

	cout << round(starDistance*100);
}

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

이 문제의 경우  최소 신장  트리 문제중 하나로 일단  최소 신장 트리를 만드는 알고리즘으로 크루스칼을 사용해서 풀었다
크루스칼 알고리즘 전전 게시물에 작성했다시피 경로의 Cost가 낮은 경로들 부터 연결을 하지만 서로의 root 가 다른 경로들 만 연결 하고 각자의 root들을 합쳐질때마다 업데이트 해주면 되는 문제 였다 

이 문제에서는 핵심적으로 4개의로직이 있다.

1. 부모를 찾는 로직

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

이 로직은 x의 부모 root를찾는 코드로 재귀적으로 부모를 찾으면서 부모를 업데이트도 해주는 코드이다

2. 같은 부모인지 찾는 로직

bool sameParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	if (x == y)
		return true;
	else
		return false;

3. 2개의 다른 트리를 합치는 로직 합칠때는 합쳐진 트리의 부모만 바꿔주면 된다

void uni(int  x, int y) {
	x = findParent(x);
	y = findParent(y);
	parent[y] = x;
}

4. cost가 낮은 순 부터 오름차순으로 입력 데이터를 정렬 한다 그후 루프를 돌면서  2번 3번 과정을 반복해준다 그후 연결된 cost중 가장  높은부분을 뺴준다 그 이유는 이문제에서 마을을 두개로 분리한다고 하였으니 가장 비용이 많이 드는 길 을 없애면 된다

	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;
			cnt += 1;
			if (cnt == v - 1) {
				cost -= inputData[i].first;
			}
		}
	}

전체 코드는 아래와 같다

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 가중치 start end순
vector<pair<int, pair<int, int>>> inputData;
int parent[100001] = { 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;
	long long cost;
	cost = 0;
	int cnt = 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;
			cnt += 1;
			if (cnt == v - 1) {
				cost -= inputData[i].first;
			}
		}
	}
	cout << cost;
}

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

이 문제는 전형 적인 그리디 문제이다 그리디 문제의 특징은 모든 과정에서의 답이아니기 때문에 풀 수 있다

이문제는 일단 주의 할점을 일반적으로 input을 받으면 int 형자료형은 50만자리의 수를 받을 수없기 때문에 string으로 input을 받아 사용하는게 좋다

또한 이문제는 스택을 두고 이전에 들어온 값들보다 현재 들어오는 값들을 뽑고 거기에 넣으면서 뽑은 횟수를 저장해야한다 그래서 만약에 최대 뽑기수보다 못뽑으면 그냥 그상태로 값이 나온다

#include<iostream>
#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
stack<long long> bigStack;
stack<long long> answerStack;
long long n, k;
string num;
vector<long long> arr;
long long popCount=0;
long long result = 0;
int main() {
	cin >> n >> k;
	cin >> num;
	for (int i = 0; i < num.length(); ++i) {
		arr.push_back(num[i] - '0');  // 문자 '0'을 빼서 실제 숫자로 변환
	}

	if(arr.size()!=0)
		bigStack.push(arr[0]);
	for (long long i = 1; i < n; i++) {
		while (!bigStack.empty()&& bigStack.top() < arr[i] && popCount<k) {
			bigStack.pop();
			popCount += 1;
		}
		bigStack.push(arr[i]);
	}
	while (popCount < k) {
		bigStack.pop();
		popCount += 1;
	}
	while (!bigStack.empty()) {
		answerStack.push(bigStack.top());
		bigStack.pop();
	}

	while (!answerStack.empty()) {
		cout << answerStack.top();
		answerStack.pop();
	}

}

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

이 문제의 경우 bfs 문제이다 

우리가 구해야 할 답은 총 3개다
1 번과 2번은 그냥 우리가 아는 bfs 로 영역의 최대 크기와 영역의 갯수를 구해주면된다
3번은 내가 있는 방을 기준으로 4방의 방에서 벽을 뚫는다고 가정하고 풀었다 그후 모든 방에서 상하좌우방을 뚫었을 때 진행할수 있으면 진행 하도록 코드를 작성 하였다

#include <iostream>
#include<bitset>
#include <queue>
#include <cstring>
using namespace  std;
int arr[50][50];
bool isVisited[50][50];
int n, m;
int maxCnt = 1;
int xi[4] = { 0,1,0,-1 };
int yi[4] = { 1,0,-1,0 };
queue<pair<int, int>> bfsq;
bool canGo(int x, int y , int z) {
	if (x >= 0 && x < m && y >= 0 && y < n && !isVisited[x][y]) {
		if (arr[x][y] & (1 << z)) {
			return false;
		}
		else
			return true;
	}
	return false;
}
bool canGo(int x, int y) {
	if (x >= 0 && x < m && y >= 0 && y < n ) {
		return true;
	}
	return false;
}

void bfs(int startX, int startY) {
	bfsq.push({ startX,startY });
	isVisited[startX][startY] = true;
	int cnt = 1;
	while (!bfsq.empty()) {
		int col = bfsq.front().first;
		int row = bfsq.front().second;
		bfsq.pop();
		for (int i = 0; i < 4; i++) {
			if (canGo(col + xi[i], row + yi[i],i)) {
				bfsq.push({ col + xi[i] , row + yi[i] });
				isVisited[col + xi[i]][row + yi[i]] = 1;
				cnt += 1;
				if (maxCnt < cnt)
					maxCnt = cnt;
			}
		}
	}
}
int main() {
	int roomCnt=0;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (isVisited[i][j])
				continue;
			roomCnt += 1;
			bfs(i, j);
		}
	}
	cout << roomCnt << endl;
	cout << maxCnt << endl;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++){
			for (int k = 0; k < 4; k++) {
				if (canGo(i + xi[k], j + yi[k]) && (arr[i + xi[k]][j + yi[k]] &(1<<k))) {
					memset(isVisited, 0, sizeof(isVisited));
					arr[i + xi[k]][j + yi[k]] ^= (1 << k);
					bfs(i, j);
					arr[i + xi[k]][j + yi[k]] |= (1 << k);
				}
			}
		}
	}

	cout << maxCnt;
}

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

이 문제는 플로이드 워셜 알고리즘을 다룬다
다익스트라는 하나의 점에서 부터 다른 vertex까지의 최단 경로를 구하는 것이라면
플로이드 워셜은 전체 점에서의 최단 경로를 구하는 문제이다

다익스트라 알고리즘의 경우 우선순위 큐에 계속 넣어서 경로의 최솟값들을 소모시키면서 다른 vertex들과의 비용을 업데이트 해줬다.

단 플로이드 워셜 알고리즘의 경우 모든 점을 업데이트 해줘야하므로 dp를 통해 순차 탐색을 진행해준다

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}

핵심 로직은 이부분이다 K라는 경유점을 통해서 i to j 의 값과 기존에 i to j의 값을 비교해서 더작으면 넣어주는게 로직이다 .

#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;

int n;
int dp[101][101];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	int m;
	cin >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				dp[i][j] = 0;
			else
				dp[i][j] = INF;
		}
	}
	for (int i = 0; i < m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		dp[from][to] = min(dp[from][to], cost);
	}
	//k는 경유점
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dp[i][j] == INF) {
				cout << 0 << ' ';
				continue;
			}
			cout << dp[i][j] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

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

이 문제는 dp의 기본적인 문제이다 이문제의 경우 동전의 종류 와 만들 수 있는 동전의 크기가 있다.
이문제는 내가 현재 들고있는 동전을 추가해서 현재의 가치를 만들때 최소한의 동저만 쓴경우만 선택해서 진행한다
한번 표로 봐보자

우리가 가진 동전으로 0원을 만들수 있는 경우의 수는 0 이다 만들수 없다
1원은 현재 1원하나로 만들고 5원 12원으로 만들기 위해서는 -4원 -11원 이 있어야 만들 수 있는데 해당 원수는 없으니 제외한다

자 쭉쭉 진행 되었을 때를 보자

이 상태 에서 10원을 만든다고 가정해보자 9원에서 1원을 추가해서 만드는 방법하나와 5원에서 5원을 하나 추가하는 방법이 있다 이경우 5원에서 동전 하나를 추가해서 만드는게 동전 2개이므로 5원에서 현재 5원을 선택해서 +1 해주는 방식으로 2를 넣어준다 

이문제의 점화식은

arr[i]=min(arr[i], arr[i - coin[j]] + 1);
내가 현재 선택한 동전을 추가했을 때 나올수 있는 경우의 수중 최소를 선택해주면 된다 전체 코드는 아래와 같다

#include <iostream>
#include <algorithm>
using namespace std;
#define INF 987654321
int n, k;
int coin[100];
int arr[10000] = { 0, };
int main() {
	cin >> n >> k;
	for(int i=0;i<n; i++){
		cin >> coin[i];
	}
	for (int i = 1; i <= k; i++) {
		arr[i] = INF;
		for (int j = 0; j < n; j++) {
			if (i - coin[j] >= 0) {
				arr[i]=min(arr[i], arr[i - coin[j]] + 1);
			}
		}
	}
	if (arr[k]==INF)
		cout << -1;
	else
		cout << arr[k];
}