급하게임개발

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

이 문제의 경우 BFS기본 문제이다 그냥 2가지 BFS를 만들어 주면 된다.

첫번째는 시작점과 같은 색깔만을 가진 영역만을 BFS로 탐색하여 영역을 카운트 해주면 된다

두번째는 시작점의 색이 R이나 G일 경우 색깔이 R이나 G인영역을 BFS로 탐색하게 해주면 된다.

#include<iostream>
#include<queue>
using namespace std;
int N;
char arr[100][100];
bool normalVisited[100][100];
bool weakVisited[100][100];
int normalBFS() {
	queue<pair<int, int>> bfsQ;
	char color;
	int count = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (normalVisited[i][j])
				continue;
			color = arr[i][j];
			normalVisited[i][j]== true;
			bfsQ.push({ i,j });
			count += 1;
			while (!bfsQ.empty()) {
				int x, y;
				x = bfsQ.front().first;
				y = bfsQ.front().second;
				bfsQ.pop();
				if (x-1>=0&&!normalVisited[x - 1][y] && arr[x - 1][y] == color) {
					bfsQ.push({ x - 1,y });
					normalVisited[x - 1][y] = true;
				}
				if (x + 1 < N && !normalVisited[x + 1][y] && arr[x + 1][y] == color) {
					bfsQ.push({ x + 1,y });
					normalVisited[x + 1][y] = true;
				}
				if (y - 1 >= 0 && !normalVisited[x][y-1] && arr[x][y-1] == color) {
					bfsQ.push({ x,y-1 });
					normalVisited[x][y-1] = true;
				}
				if (y + 1 < N && !normalVisited[x][y + 1] && arr[x][y + 1] == color) {
					bfsQ.push({ x,y + 1 });
					normalVisited[x][y + 1] = true;
				}

			}
			
		}
	}
	return count;
}
int WeakBFS() {
	queue<pair<int, int>> bfsQ;
	char color;
	int count = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (weakVisited[i][j])
				continue;
			color = arr[i][j];
			weakVisited[i][j] == true;
			bfsQ.push({ i,j });
			count += 1;
			while (!bfsQ.empty()) {
				int x, y;
				x = bfsQ.front().first;
				y = bfsQ.front().second;
				bfsQ.pop();
				if (color == 'R' || color=='G') {
					if (x - 1 >= 0 && !weakVisited[x - 1][y] && (arr[x - 1][y] == 'R' || arr[x - 1][y] == 'G')) {
						bfsQ.push({ x - 1,y });
						weakVisited[x - 1][y] = true;
					}
					if (x + 1 < N && !weakVisited[x + 1][y] && (arr[x + 1][y] == 'R' || arr[x + 1][y] == 'G')) {
						bfsQ.push({ x + 1,y });
						weakVisited[x + 1][y] = true;
					}
					if (y - 1 >= 0 && !weakVisited[x][y - 1] && (arr[x][y-1] == 'R' || arr[x][y-1] == 'G')) {
						bfsQ.push({ x,y - 1 });
						weakVisited[x][y - 1] = true;
					}
					if (y + 1 < N && !weakVisited[x][y + 1] && (arr[x][y+1] == 'R' || arr[x][y+1] == 'G')) {
						bfsQ.push({ x,y + 1 });
						weakVisited[x][y + 1] = true;
					}
				}
				else {
					if (x - 1 >= 0 && !weakVisited[x - 1][y] && arr[x - 1][y] == color) {
						bfsQ.push({ x - 1,y });
						weakVisited[x - 1][y] = true;
					}
					if (x + 1 < N && !weakVisited[x + 1][y] && arr[x + 1][y] == color) {
						bfsQ.push({ x + 1,y });
						weakVisited[x + 1][y] = true;
					}
					if (y - 1 >= 0 && !weakVisited[x][y - 1] && arr[x][y - 1] == color) {
						bfsQ.push({ x,y - 1 });
						weakVisited[x][y - 1] = true;
					}
					if (y + 1 < N && !weakVisited[x][y + 1] && arr[x][y + 1] == color) {
						bfsQ.push({ x,y + 1 });
						weakVisited[x][y + 1] = true;
					}
				}

			}

		}
	}
	return count;
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}
	cout <<normalBFS()<<" "<< WeakBFS();
}

이 문제의 경우 기본적인 BFS문제들을 여러문제 풀어봤으면 매우 쉽게 해결방법이 떠올랐을 문제이다

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

이 문제의 경우 생각해줘야할 게 많았다 일반 Bfs지만 문제를 잘 읽지 않으면 틀린다

이문제에서 간과하면 안될 조건이 있다.

1. 시작점에 사다리와 뱀이 여러개 놓일 수는 없지만 도착점은 상관없다.

2. 뱀과 사다리를 만나면 무조건 이동한다 이다 즉 발판을 밟지 못한다.

이 위를 생각하고 풀어야 빠른시간안에 풀 수 있었다 필자는 이 부분을 캐치하지 못 해 오랜시간이 걸렸다.

#include <iostream>
#include <queue>
using namespace std;
int arr[101];
int visited[101];
int radder[101];
queue<int> bfsq;
int solution() {
	bfsq.push(1);
	while (!bfsq.empty()) {
		int start = bfsq.front();
		bfsq.pop();
		if ((start + 6 <= 100) && !visited[start + 6]) {
			if (radder[start + 6] > 0) {
				if (visited[radder[start + 6]] == 0) {
					visited[radder[start + 6]] = visited[start] + 1;
					bfsq.push(radder[start + 6]);
				}
			}
			else if (radder[start + 6] == 0) {
				visited[start + 6] = visited[start] + 1;
				bfsq.push(start + 6);
			}
			if (start + 6 == 100)
				return visited[start + 6];
		}
		if ((start + 5 <= 100) && !visited[start + 5]) {
			if (radder[start + 5] > 0) {
				if (visited[radder[start + 5]] == 0) {
					visited[radder[start + 5]] = visited[start] + 1;
					bfsq.push(radder[start + 5]);
				}
			}
			else if (radder[start + 5] == 0) {
				visited[start + 5] = visited[start] + 1;
				bfsq.push(start + 5);
			}
			if (start + 5 == 100)
				return visited[start + 5];
		}
		if ((start + 4 <= 100) && !visited[start + 4]) {
			if (radder[start + 4] > 0) {
				if (visited[radder[start + 4]] == 0) {
					visited[radder[start + 4]] = visited[start] + 1;
					bfsq.push(radder[start + 4]);
				}
			}
			else if (radder[start + 4] == 0) {
				visited[start + 4] = visited[start] + 1;
				bfsq.push(start + 4);
			}
			if (start + 4 == 100)
				return visited[start + 4];
		}
		if ((start + 3 <= 100) && !visited[start + 3]) {
			if (radder[start + 3] > 0) {
				if (visited[radder[start + 3]] == 0) {
					visited[radder[start + 3]] = visited[start] + 1;
					bfsq.push(radder[start + 3]);
				}
			}
			else if (radder[start + 3] == 0) {
				visited[start + 3] = visited[start] + 1;
				bfsq.push(start + 3);
			}
			if (start + 3 == 100)
				return visited[start + 3];
		}
		if ((start + 2 <= 100) && !visited[start + 2]) {
			if (radder[start + 2] > 0) {
				if (visited[radder[start + 2]] == 0) {
					visited[radder[start + 2]] = visited[start] + 1;
					bfsq.push(radder[start + 2]);
				}
			}
			else if (radder[start + 2] == 0) {
				visited[start + 2] = visited[start] + 1;
				bfsq.push(start + 2);
			}
			if (start + 2 == 100)
				return visited[start + 2];
		}
		if ((start + 1 <= 100) && !visited[start + 1]) {
			if (radder[start + 1] > 0) {
				if (visited[radder[start + 1]] == 0) {
					visited[radder[start + 1]] = visited[start] + 1;
					bfsq.push(radder[start + 1]);
				}
			}
			else if (radder[start + 1] == 0) {
				visited[start + 1] = visited[start] + 1;
				bfsq.push(start+1);
			}
			if (start + 1 == 100)
				return visited[start + 1];
		}
	}
}
int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N+M; i++) {
		int from, to;
		cin >> from>> to;
		radder[from] = to;
	}

	cout << solution();
}

코드가 길지만  사실 실제로 보면 얼마 안되는 양이다.

일단 주목해야할 부분은

		if ((start + 6 <= 100) && !visited[start + 6]) {
			if (radder[start + 6] > 0) {
				if (visited[radder[start + 6]] == 0) {
					visited[radder[start + 6]] = visited[start] + 1;
					bfsq.push(radder[start + 6]);
				}
			}
			else if (radder[start + 6] == 0) {
				visited[start + 6] = visited[start] + 1;
				bfsq.push(start + 6);
			}
			if (start + 6 == 100)
				return visited[start + 6];
		}

이 부분이다 이부분의 경우느 일단 우리가 방문할려는 지점이 방문되었는지 또한 우리가 방문할 발판이 100을 넘었는지를 검사한다. 넘으면 실행 하지 않는다 그후 사다리나 뱀이 있다면 그 발판을 밟지 않고 이어져있는 발판을 밟는다 그 후 이를 bfs에 넣는다. 만약 사다리나 뱀이없으면 해당 발판을 밟는다. 이게 풀이 로직이었다. 

코테에서 항상 중요한 점은 빠른시간안에 반례체킹을 하는 것인거 같다.

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

이 문제는 나의 부족한 머리로는 혼자 생각 할 수 없는 알고리즘이었다.

하지만 이번 문제를 푼 것을 계기로 똑같은 유형의 문제는 틀리지 않아야 겠다.

일단 풀이는 우선순위 큐 2개로 중간 값을 구하는 방법을 알아야 한다

이게 알파이자 오메가였다.

우선순위 큐로 2개의 값을 구하는 방법은

1. MaxHeap은 무조건 MinHeap보다 사이즈가 하나 커야 한다.

2. MaxHeap의 최대값은 MinHeap의 최솟값 보다 작아야 한다. 이 조건을 만족하지 않을 시

maxHeap의 최대값과 MinHeap의 최솟값을 swap해준다.

이 법칙을 지키면 MaxHeap의 최대값은 항상 중간값이 된다.

이 풀이를 위의 문제에서 주어진 예제에 대해서 대입해보겠다.

이런 순서대로 트리가 차면서 항상 Maxheap의 최대값이 중간값을 나타내고 있다. 

코드는 아래와 같다

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int,vector<int>,less<int>> maxq;
priority_queue<int, vector<int>, greater<int>> minq;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N;
	cin >> N;
	int inputNum;
	cin >> inputNum;
	maxq.push(inputNum);
	cout << maxq.top() << '\n';
	for (int i = 1; i < N; i++) {
		cin >> inputNum;
		if (maxq.size() == minq.size())
			maxq.push(inputNum);
		else {
			minq.push(inputNum);
		}
		if (!maxq.empty() && !minq.empty() && !(maxq.top() < minq.top())) {
			int a = maxq.top();
			int b = minq.top();

			maxq.pop();
			minq.pop();

			minq.push(a);
			maxq.push(b);
		}
		cout << maxq.top()<<'\n';
	}
}

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

이 문제의 겨우  testcase는 다맞게 나오는데 이상하게 계속 틀렸다고 나왔다. 이에 계속 틀린이유를 찾느라 시간을 많이 소비했다

일단 이문제의 경우 2가지의 경우를 생각해주어야한다

시작점-V1-V2-종점

시작점-V2-V1-종점

여기서 문제에서 시작점에서 V1-V2를 경우하여 종점을 가는것이기에 종점 부터 가는 경우의 수는 생각 해 줄 필요가 없다.

당연히 Vertext와 Edge에 관한 문제이기에 익숙한 다익스트라를 활용했다.

#include <iostream>
#include <queue>
#include <vector>
#include<algorithm>
#define INT_MAX 987654321
using namespace std;
int N, E;
priority_queue < pair<int, int>, vector<pair<int, int>>, greater <pair<int, int>>> djikstra_pq;
vector<pair<int, int>> djikstra_v[801];
vector<int> distanceV(801);
void djikstra(int i) {
	int start = i;
	int toCost = 0;
	djikstra_pq.push({ toCost,start });
	distanceV[start] = 0;
	while (!djikstra_pq.empty()) {
		int toCost = djikstra_pq.top().first;
		int toVertex = djikstra_pq.top().second;
		
		djikstra_pq.pop();
		int distanceToNextVertex = distanceV[toVertex];
		if (distanceToNextVertex < toCost) {
			continue;
		}
		for (int i = 0; i < djikstra_v[toVertex].size(); i++) {
			int cost = djikstra_v[toVertex][i].first + toCost;
			int nextIdx = djikstra_v[toVertex][i].second;
			if (cost < distanceV[nextIdx]) {
				distanceV[nextIdx] = cost;
				djikstra_pq.push({ cost,nextIdx });
			}
		}
		
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> E;
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		djikstra_v[a].push_back({ c,b });
		djikstra_v[b].push_back({ c,a });
	}
	int v1, v2;
	cin >> v1 >> v2;
	int sToV1, sToV2, v1ToV2, v1ToN, v2ToN;
	distanceV.assign(N+1, INT_MAX);
	djikstra(1);
	sToV1 = distanceV[v1];
	sToV2 = distanceV[v2];
	distanceV.assign(N+1, INT_MAX);
	djikstra(v1);
	v1ToV2 = distanceV[v2];
	v1ToN = distanceV[N];
	distanceV.assign(N+1, INT_MAX);
	djikstra(v2);
	v2ToN = distanceV[N];

	int ans = INT_MAX;

	ans = min(ans, sToV1 + v1ToV2 + v2ToN);
	ans = min(ans, sToV2 + v1ToV2 + v1ToN);

	if ((v1ToV2 == INT_MAX)||ans==INT_MAX) {
		cout << -1;
	}
	else {
		cout << ans;
	}
}

내가 이렇게 작성한 코드에서 climits에 INT_MAX를 사용하면 오류가 났다 아마도 테스트케이스중 지나가지 않은 경로에대한 값을 출력할 때 climits에 INT_MAX를 사용하면 값이 오바되면서 최종출력값에 오류가 날것으로 추측했다 이에 Vertex의 최대갯수 800 그리고 가중치의 최대갯수 1000 그리고 구간을 3개로 나누었기에 3을곱한값보다 크지만 INT_MAX보다 작은 값을 최대값으로 지정해주고 풀었다

테스트케이스가 맞을 때 틀렸습니다가 계속 나올 경우 이부분도 생각해서 풀면 좋을거 같다

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

이 문제의 경우 쉬운 전형적인 bfs문제이다. 모든 정점을 시작점으로 bfs를 돌린다 그 후 정점을 시작점으로 돌리는 케이스마다의 각 정점의 layer의 합을 저장한 후 이를 비교하여 최솟값을 갖는 정점의 값을 출력해 주면 되는 문제였다

bfs의 기본적이 풀이 로직은 이 블로그의 다른글들에 있다. 코드는 아래와 같다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, M;
vector<int> bfsv[101];
int arr[101] = { 0, };
int main() {
	queue<pair<int, int>> bfsq;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;
		bfsv[temp1].push_back(temp2);
		bfsv[temp2].push_back(temp1);
	}
	for (int i = 1; i <= N; i++) {
		int start = i;
		bfsq.push({ start,0 });
		bool isVisited[101] = { 0, };
		while (!bfsq.empty()) {
			int front = bfsq.front().first;
			int second = bfsq.front().second;
			arr[front] += second;
			isVisited[front] = true;
			bfsq.pop();
			for (int j = 0; j < bfsv[front].size(); j++) {
				if (!isVisited[bfsv[front][j]]) {
					bfsq.push({ bfsv[front][j], second + 1 });
					isVisited[bfsv[front][j]] = true;
				}
			}
		}
	}
	int min=5001;
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (min > arr[i]) {
			ans = i;
			min = arr[i];
		}
	}
	cout << ans;
}

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

이 문제는 브루트 포스 문제이다 범위가 500000으로 확정되었기 때문에  특정 범위 안에 있는 수들이 조건이 맞는지만 판별해주면 되는 분제였다 나는 수빈이가 이동하려는 범위의 2배를 채널 선택의 범위로 정하였다.

일단 나는 수빈이가 선택하려는 채널을 기준으로 증가하는 채널과 감소하는 채널 2개를 선택해 2개중에 더 작은 값을 사용하는 방법을 사용하였다

위 그림처럼 변수 psearch와 nsearch를 만들어 

수빈이가 선택한 채널을 기준으로 더큰채널과 더작은 채널 중 증가와 감소로 접근할 수 있는 범위를 찾고 자릿수 입력도 입력수에 포함하기 때문에 +-버튼 클릭수와 채널의 자릿수를 더해서 비교후 더 작은값을 저장해준다.

여기에서 추가로 또 예외처리 해줘야 할게 있는데

수빈이의 채널이 100부터 시작하기에 만약 채널이 100부터 시작했을 때 더 가까울 경우도 생각해주어야 한다.

해당 그림을 통해 구현한 코드는 아래와 같다

#include<iostream>
#include<stdlib.h>
int N,M;
bool arr[10];
int psearch = 1000000;  
int nsearch = 1000000;
int hsearch;
using namespace std;
int solution(int n) {
	if (n < 10) {
		if (!arr[n]) {
			return 1;
		}
	}
	else if (n < 100) {
		if (!arr[n / 10] && !arr[n % 10]) {
			return 2;
		}
	}
	else if (n < 1000) {
		if (!arr[n/100] && !arr[n%100 / 10] && !arr[n % 10]) {
			return 3;
		}
	}
	else if (n < 10000) {
		if (!arr[n/1000] && !arr[n%1000 / 100] && !arr[n%100 / 10] && !arr[n % 10]) {
			return 4;
		}
	}
	else if (n < 100000) {
		if (!arr[n / 10000] && !arr[n%10000 / 1000] && !arr[n%1000 / 100] && !arr[n%100 / 10] && !arr[n % 10]) {
			return 5;
		}
	}
	else if(n<1000000){
		if (!arr[n / 100000] && !arr[n%100000 / 10000] && !arr[n%10000 / 1000] && !arr[n%1000 / 100] && !arr[n%100 / 10] && !arr[n % 10]) {
			return 6;
		}
	}
	return false;
}
int main() {
	cin >> N >> M;
	int searchNum1,searchNum2;
	int answer = 0;
	for (int i = 0; i < M; i++) {
		int temp;
		cin >> temp;
		arr[temp] = true;
	}
	searchNum1 = N;
	searchNum2 = N;


	while (true) {
		if (solution(searchNum1) && (searchNum1 >= 0)) {
			psearch = solution(searchNum1) + (N - searchNum1);
			break;
		}
		searchNum1--;
		if (searchNum1 < 0)
			break;
	}

	while (true) {
		if (solution(searchNum2) && (searchNum1 <=1000000)) {
			nsearch = solution(searchNum2) + (searchNum2-N);
			break;
		}
		searchNum2++;
		if (searchNum2 > 1000000)
			break;
	}
	hsearch = abs(N - 100);
	if (psearch > nsearch) {
		answer = nsearch;
	}
	else {
		answer = psearch;
	}

	if (answer > hsearch) {
		answer = hsearch;
	}

	cout << answer;
}

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];
}