급하게임개발

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

이 문제는 그냥 크루스칼 알고리즘인데 출력이 불친절하다 그냥 00전에 테스트케이스가 여러개 나오는 문제였다

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int parent[200000];
int n, m;
vector<pair<int, pair<int, int>>> inputData;

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

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

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

int main() {
    while (true) {
        cin >> n >> m;
        if (n == 0 && m == 0) break; // 종료 조건

        inputData.clear();
        int tmp1, tmp2, tmp3;
        int cost = 0, totalCost = 0;

        for (int i = 0; i < m; i++) {
            cin >> tmp1 >> tmp2 >> tmp3;
            inputData.push_back({ tmp3, {tmp1, tmp2} });
            totalCost += tmp3;
        }

        // 초기화
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        sort(inputData.begin(), inputData.end()); // 간선 정렬

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

        cout << totalCost - cost << "\n";
    }

    return 0;
}

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

이 문제는 RGB거리 문제의 발전형이다 기존에는 사이클을 검사안했으나 이번에는 사이클을 검사해야한다 그래서 이문제를 풀기위한 핵심은
첫번째 집의 색깔을 정해주고 나머지 집들의 dp를 돌리는 것이다

어떻게 정하면 되는지는 우리는 원래 dp 를 풀때 각라인의 최솟값을 넣는데 이 최솟값을 만들 때 우리는 나머지 선택을 하지못하게 하면된다

해당 예제를 예시로 보자

평소에 우리가 dp를 구할  때 우리는 26 40 83을 min 때리고 이를 바탕으로 다음라인에서 비교 해준다 평소대로 하게된다면 우리는 다음  dp 행을 구할 때 최소 색깔을 선택함으로 우리가 색을 정할 수가 없다 만약에 우리가 999999 40 999999 이런식으로 dp 행을 놓게 된다면 무조건적으로 40이 선택된다 이러한 로직을 바탕으로

	for (int first = 0; first < 3; first++) {
		for (int i = 0; i < 3; i++) {
			if (first == i) {
				dp[0][i] = arr[0][i];
			}
			else {
				dp[0][i] = maxVal;
			}
		}

해당 로직이 작성된다 first는 첫번째 집이 고른 색이다 첫번째 집이 빨간색을 골랐을 때 우리는 파란색 초록색을 고르는 선택지를 없애버리기 위해서 dp행이 첫번째의 고를 선택지 에서 지워버리는 것이다



이로직 뺴고는 dp 점화식 자체는 별반 다른지 않다

내가 빨간색을 선택했을 때 이전에 초록색 혹은 파란색을 선택했을 때 의 값중 최솟 값을 선택하면된다 

즉 점화식 자체는

	for (int i = 1; i < n; i++) {
		dp[i][0] = arr[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
		dp[i][1] = arr[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
		dp[i][2] = arr[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
	}

이렇게 된다

전체 코드는 아래와 같다

#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001][3];
int dp[1001][3];
int maxVal = 987654321;
int answer = 987654321;
int n;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> arr[i][j];
		}
	}

	for (int first = 0; first < 3; first++) {
		for (int i = 0; i < 3; i++) {
			if (first == i) {
				dp[0][i] = arr[0][i];
			}
			else {
				dp[0][i] = maxVal;
			}
		}

		for (int i = 1; i < n; i++) {
			dp[i][0] = arr[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
			dp[i][1] = arr[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
			dp[i][2] = arr[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
		}

		for (int i = 0; i < 3; i++) {
			if (first == i)
				continue;
			answer = min(answer, dp[n-1][i]);
		}
	}

	cout << answer;
}

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

이 문제는 3개를 어떻게 할까 고민하다가 그냥 1개를 정해놓고 0의 가장 가까운 투포인터를 하면 되겠다는 생각을 했다 즉 하나의수는 고정인 상태에서 0보다크면 혹은 작으면 에 대해서 m값과 r값을 바꿔주면서 최솟값을 저장하는 방식으로 진행했다

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
using namespace std;
int n;
vector<long long> inputData;
long long result = 3000000001;
long long ans[3];
int main() {
	cin >> n;

	long long tmp;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		inputData.push_back(tmp);
	}
	sort(inputData.begin(), inputData.end());
	int l, m, r;
	for (int l = 0; l < n - 2; l++) {
		m = l + 1;
		r = n - 1;
		while (m < r) {
			long long val = inputData[l] + inputData[m] + inputData[r];
			if (abs(val) < result) {
				result = abs(val);

				ans[0] = inputData[l];
				ans[1] = inputData[m];
				ans[2] = inputData[r];
			}
			if (val < 0) {
				m++;
			}
			else {
				r--;
			}
		}
	}

	for (int i = 0; i < 3; i++) {
		cout << ans[i] << " ";
	}
}

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

이 문제는 겁나 복잡해보였지만 막상 풀고나니 이해하기 쉬웠다

그냥 두가지 케이스 빨간공 파란공 각각 움직인다음 겹칠때 혹은 구멍에 들어갈때의 조건식만 추가해주면 되었다

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int arr[10][10];
struct INFO {
	int Rx, Ry, Bx, By, count;
};
int n, m;
INFO start;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int visited[11][11][11][11] = { 0, };
int bfs() {
	queue<INFO> bfsQ;
	bfsQ.push(start);

	int ans = -1;
	visited[start.Rx][start.Ry][start.Bx][start.By] = 1;
	while (!bfsQ.empty()) {
		INFO cur = bfsQ.front();
		bfsQ.pop();
		if (cur.count > 10)break;

		if (arr[cur.Rx][cur.Ry] == 4 && arr[cur.Bx][cur.By] != 4) {
			ans = cur.count;
			break;
		}

		for(int i=0; i<4; i++){
			int nextRy = cur.Ry;
			int nextRx = cur.Rx;
			int nextBy = cur.By;
			int nextBx = cur.Bx;
			while (1) {
				if (arr[nextRx][nextRy] != 1 and arr[nextRx][nextRy] != 4) {
					nextRx += dx[i];
					nextRy += dy[i];
				}
				else {
					if (arr[nextRx][nextRy] == 1) {
						nextRx -= dx[i]; 
						nextRy -= dy[i]; //벽일 경우 이전위치로
					}
					break;
				}
			}

			//blue 구슬 벽이나 구멍일때까지 한 방향으로 이동함
			while (1) {
				if (arr[nextBx][nextBy] != 1 and arr[nextBx][nextBy] != 4) {
					nextBx += dx[i];
					nextBy += dy[i];
				}
				else {
					if (arr[nextBx][nextBy] == 1) {
						nextBx -= dx[i]; 
						nextBy -= dy[i]; //벽일 경우 이전위치로
					}
					break;
				}
			}

			//red와 blue가 겹칠 경우
			if (nextRx == nextBx and nextRy == nextBy) {
				if (arr[nextRx][nextRy] != 4) {
					int red_dist = abs(nextRx - cur.Rx) + abs(nextRy - cur.Ry);
					int blue_dist = abs(nextBx - cur.Bx) + abs(nextBy - cur.By);

					if (blue_dist > red_dist) {
						nextBx -= dx[i];
						nextBy -= dy[i];
					}
					else {
						nextRx -= dx[i];
						nextRy -= dy[i];
					}
				}
			}

			//방문여부 확인
			if (visited[nextRx][nextRy][nextBx][nextBy] == 0) {
				visited[nextRx][nextRy][nextBx][nextBy] = 1;
				INFO next;
				next.Rx = nextRx;
				next.Ry = nextRy;
				next.Bx = nextBx;
				next.By = nextBy;
				next.count = cur.count + 1;

				bfsQ.push(next);

			}
		}

	}
	return ans;
}

int main() {
	cin >> n >> m;
	string input;

	for (int i = 0; i < n; i++) {
		cin >> input;
		for (int j = 0; j < m; j++) {
			if (input[j] == '#') {
				arr[i][j] = 1;
			}
			else if (input[j] == 'R') {
				arr[i][j] = 2;
				start.Rx = i;
				start.Ry = j;
			}
			else if (input[j] == 'B') {
				arr[i][j] = 3;
				start.Bx = i;
				start.By = j;
			}
			else if (input[j] == 'O') {
				arr[i][j] = 4;
			}
		}
	}
	start.count = 0;
	cout << bfs();
}

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

이 문제는 이분탐색 문제이다 처음 그냥 대충  쉽게 접근하다가 틀렸는데 같은수가 여러번 들어갈수 있음을 망각했다

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
long long  n;
vector<long long > inputData;
int main() {
	cin >> n;
	long long  tmp;
	long long  cnt = 0;

	for (long long i = 0; i < n; i++) {
		cin >> tmp;
		inputData.push_back(tmp);
	}
	sort(inputData.begin(), inputData.end());

	for (long long i = 0; i < n; i++) {
		long long left = n-1;
		long long right = 0;
		
		while (right <n && left>=0  && right<left) {
			if (right == i) {
				if (right < n-1) {
					right += 1;
				}
			}
			if (left == i) {
				if (left > 0) {
					left -= 1;
				}
			}
			if (left == right) {
				break;
			}
			if ((inputData[right] + inputData[left]) == inputData[i]) {
				cnt += 1;
				break;
			}
			else if ((inputData[right] + inputData[left]) > inputData[i]) {
				left -= 1;
			}
			else if ((inputData[right] + inputData[left]) < inputData[i]) {
				right += 1;
			}
		}
	}
	cout << cnt;
}

전체 코드는 이렇게 된다 처음에는 2/n 기준으로 양옆으로 펼쳐지면서 값을 찾으려 했으나 이렇게 하면 못찾을 때 가 발생해서 양옆에서 조이는 방식으로 진행 했다

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

이 문제는 그냥 여러개 섞어놓은 문제이다 병사를 배정하는것은 조합으로 dfs로 풀면 되고 
병사들이 몬스터를 잡는건 bfs로 풀면된다 조합에대한 모든것을 bfs함으로 브루트포스이기도 하다 사실이문제는 단지 기본적인 알고리즘 여러개를 섞어놓은것이다
주의할 점은 bfs를 할때

int goX[3] = { 0,-1,0};
int goY[3] = { -1,0,1};

이 순서대로 해야한다 bfs가 거리가 가까운거는 보장하지만 왼쪽 탐색을 하기위해서는 해당 인덱스를 따라 해야지 왼쪽부터 탐색한다
또한 탐색하자마자 바로 0으로 바꾸지말고 중복으로 한 몬스터를 때릴수 있으므로 4로 체크하고 이후에 0으로 바꾼다

#include <iostream>
#include <stdlib.h>
#include <queue>
using namespace std;
int originArr[16][15];
int copyArr[16][15];
int N, M, D;
int goX[3] = { 0,-1,0};
int goY[3] = { -1,0,1};
int maxNum;
bool isVisited[16][15] = { 0, };
bool AllDie() {
	bool isDie = true;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (copyArr[i][j] == 1)
				isDie = false;
		}
	}
	return isDie;
}
void CopyOrigin() {
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			copyArr[i][j] = originArr[i][j];
		}
	}
}
bool CanGo(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < M ) {
		return true;
	}
	else {
		return false;
	}
}
void downEnemy() {
	for (int i = N-1 ; i > 0; i--) {
		for (int j = 0; j < M; j++) {
			copyArr[i][j] = copyArr[i - 1][j];
			if (copyArr[i][j] == 4)
				copyArr[i][j] = 0;
		}
	}
	for (int i = 0; i < M; i++) {
		copyArr[0][i] = 0;
	}
}
int bfs(int armyX, int armyY) {
	queue<pair<int, pair<int, int>>> ArmyQ;
	ArmyQ.push({ 0,{armyX,armyY} });
	int count = 0;
	while (!ArmyQ.empty()) {
		int curX = ArmyQ.front().second.first;
		int curY = ArmyQ.front().second.second;
		int cost = ArmyQ.front().first;
		ArmyQ.pop();
		if (cost > D)
			break;
		if (copyArr[curX][curY] == 4) {
			break;
		}
		if (copyArr[curX][curY] == 1) {
			copyArr[curX][curY] = 4;
			count += 1;
			break;
		}

		for (int i = 0; i < 3; i++) {
			int nextX = curX + goX[i];
			int nextY = curY + goY[i];
			if (CanGo(nextX, nextY)) {
				ArmyQ.push({ cost + 1,{nextX,nextY} });
			}
		}
	}
	return count;
}
void dfs(int start, int count) {
	if (count == 3) {// 병사를 3명 다배치 했을 경우
		CopyOrigin();
		int num = 0;
		while (!AllDie()) {
			for (int i = 0; i < M; i++) {
				if (copyArr[N][i] == 3) {
					num += bfs(N, i);
				}
			}
			downEnemy();
		}
		maxNum = max(num, maxNum);
	}
	
	else {
		for (int i = start+1; i < M; i++) {
			originArr[N][i] = 3;
			dfs(i, count + 1);
			originArr[N][i] = 2;
		}
	}
}
int main() {
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> originArr[i][j];
		}
	}
	for (int i = 0; i < M; i++) {
		originArr[N][i] = 2;
	}
	for (int i = 0; i < M; i++) {
		originArr[N][i] = 3;
		dfs(i, 1);
		originArr[N][i] = 2;
	}
	cout << maxNum;
}

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

이 문제는 그리드를 이용한 dfs이다 즉 dfs의 탐색방향을 그리디를 통해 정해주게 되는것이다 우리는 오른쪽 부터 왼쪽으로 파이프를 순서대로 연결할건데 이때 파이프는 오른쪽 ,오른쪽 아래 ,왼쪽 아래 이렇게 만 움직일수있는데 우리가 오른쪽부터 파이프를 놓는데 진행중에 왼쪽 방향으로 탐색을 진행하게되면 파이프가 쭉 왼쪽으로 가면서 다른애들의 연결을 막게된다 왼쪽부터 탐색할거면 반대로 놓아도 되긴 한다

#include<iostream>
using namespace std;
int R, C;
int arr[10001][501];
int cnt = 0;
int dr[3] = { -1, 0, 1 };
int dc[3] = { 1, 1, 1 };
bool canGo(int r, int c) {
	if (!arr[r][c] && r >= 0 && r < R && c >= 0 && c < C)
		return true;
	else
		return false;
}
bool dfs(int r, int c) {
	if (c== C - 1) {
		cnt += 1;
		return true;
	}
	else {
		arr[r][c] = 1;
		for (int i = 0; i < 3; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (canGo(nr, nc)) {
				if (dfs(nr, nc)) {
					return true;
				}
			}
		}
		return false;
	}
}
int main() {
	cin >> R >> C;
	string inputStr;
	for (int i = 0; i < R; i++) {
		cin >> inputStr;
		for (int j = 0; j < C; j++) {
			if (inputStr[j] == '.')
				arr[i][j] = 0;
			else
				arr[i][j] = 1;
		}
	}

	for (int i = 0; i < R; i++) {
		dfs(i, 0);
	}

	cout << cnt;
	return 0;
}

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

이 문제의 경우 일반 크루스칼을 이용하여 모든 행성간의 거리를 계산해서 하려고 하다보니 메모리 초과가 발생하였다.
이 문제의 경우 해결방식은 행성의 x,y,z 좌표를 추출한 후 각각의 Vector에 저장한뒤  해당 Vector를 정렬해준 후 차이를 계산하여 그 값을 바탕으로 크루스칼 알고리즘을 돌리는 것이었다

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
vector<pair<int, pair<int, int>>> inputData;
int parent[100001];
vector<pair<int, int>> v[3];
int n;
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() {
	cin >> n;
	int tmp1, tmp2, tmp3;
	for (int i = 0; i < n; i++) {
		cin >> tmp1 >> tmp2 >> tmp3;
		v[0].push_back({ tmp1,i });
		v[1].push_back({ tmp2,i });
		v[2].push_back({ tmp3,i });
	}
	sort(v[0].begin(), v[0].end());
	sort(v[1].begin(), v[1].end());
	sort(v[2].begin(), v[2].end());
	int cost = 0;
	for (int i = 0; i < n - 1; i++)
	{
		inputData.push_back(make_pair(abs(v[0][i].first - v[0][i + 1].first), make_pair(v[0][i].second, v[0][i + 1].second)));
		inputData.push_back(make_pair(abs(v[1][i].first - v[1][i + 1].first), make_pair(v[1][i].second, v[1][i + 1].second)));
		inputData.push_back(make_pair(abs(v[2][i].first - v[2][i + 1].first), make_pair(v[2][i].second, v[2][i + 1].second)));
	}
	sort(inputData.begin(), inputData.end());
	for (int i = 0; i < n; 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;
}

전체 코드는 이렇게 된다 일단 크루스칼의 기본 함수는 알것이라 생각하고 설명을 생략한다

	for (int i = 0; i < n; i++) {
		cin >> tmp1 >> tmp2 >> tmp3;
		v[0].push_back({ tmp1,i });
		v[1].push_back({ tmp2,i });
		v[2].push_back({ tmp3,i });
	}

자 이코드는 사용이유가 우리는 어차피 x간의 차와 y간의 차가 z간의 차가 가장 작은것을 이용해서 문제를 해결할것이므로 이렇게 각각 분리해서 인풋받는다 i는 vertex의 번호다
 그후 정렬을 해주는데 정렬을 하면 각좌표별로 크기별로 정렬이 될것이므로 무조건 나의 다음 vertex와의 거리가 연결 cost가 될거이다 다음다음꺼는 봐줄필요가 없는게 어차피 x값기준으로 만 연산을 할건데 멀리 있으면 연산 할필요가 없기 때문이다

이이후는 일반 크루스칼과 같다

	for (int i = 0; i < n - 1; i++)
	{
		inputData.push_back(make_pair(abs(v[0][i].first - v[0][i + 1].first), make_pair(v[0][i].second, v[0][i + 1].second)));
		inputData.push_back(make_pair(abs(v[1][i].first - v[1][i + 1].first), make_pair(v[1][i].second, v[1][i + 1].second)));
		inputData.push_back(make_pair(abs(v[2][i].first - v[2][i + 1].first), make_pair(v[2][i].second, v[2][i + 1].second)));
	}

이런식으로 vertex간 x거리 y거리  z거리를 넣는데 나의 다음거와의 거리만 넣어서 최솟값만 넣는다 중복이 나중에 발생해도 우리는 이 inputData를 정렬할거기 때문에 무조건 짧은 거와 연결된다