급하게임개발

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

이 문제는 내가 처음 접한 외판원 순회 문제이다 처음에는 브루트포스와 백트래킹을 사용하여 모든 경우의 수를 돌면서 최소의 값을 출력하려고 했으나 시간복잡도가 오바가 될것으로 판단되어 다른사람들의 풀이를 보니 비트마스킹과 dp를 조합하여 이미 방문한  노드의 대해서는 검사하지 않는 다는 것을 파악한 상태로 알고리즘을 구현하였다.

int n, map[16][16];
int dp[16][1 << 16];

n은 우리가 input 받을 노드의 수다
그리고 dp 배열에 우리는 [1<<16]을 해주는데  이것의 의미는 0번 부터 15번을 방문 하지 않았다고 초기화 시켜 놓는 것이다

우리는 깊이 우선 탐색을 통해 해당 알고리즘을 풀것이다 자 이런 외판원 문제는 무조건 사이클을 갖고 있다 그럼으로 어느 한지점을 start 및 Endpoint로 잡아도 값이 똑같이 나온다 필자는 0을 StartPoint를 두고 풀겠다

    if (visit == (1 << n) - 1) { //탐색 완료
        if (map[cur][0] == 0) //이동불가능
            return INF;
        return map[cur][0];
    }

자 이조건 부터 보자 visit의 값 즉 우리가 어느 노드를 방문했는지를 나타내는 visit값이 2의 n승 -1은 n-1 번까지 다 1이된다 즉 0부터  n-1  노드까지 n개의 노드를 다 방문 했다는 것을 의미한다 다 방문했는데 map[cur][0]은 0번으로 돌아갈수 있는 길이 없다는 것을  의미한다. 이럴경우 이동이 불가능 하다

자 이조건을 통과한후

    if (dp[cur][visit] != -1) 
        return dp[cur][visit];

이 조건을 보자 이조건의 의미는 이미 방문한 상태값을 가지고 이미 탐색한적이 있으면 더이상 탐색하지 않는다는 얘기다
즉 우리가 이전에 dp를 초기화 -1 로 초기화 시켜놓았는데 dp[cur][0101] 이 -1이 아니면 우리는 0번과 2번을 방문한 상태에서의 dfs를 돌렸다는 얘기이다 이때 우리는  이를 다시 할 필요 없으므로 해당 값을 return 해준다  자 여기 까지 왔으면

    for (int i = 0; i < n; i++) {
        if (map[cur][i] == 0) //길 X
            continue;
        if ((visit & (1 << i)) == (1 << i)) //이미 방문
            continue;
        dp[cur][visit] = min(dp[cur][visit], map[cur][i] + dfs(i, visit | 1 << i));
    }

이 로직이 남았다 이 로직의 경우 현재 어디어디를 방문하고 현재 내위치에서 갈수 있는 영역을 탐색한다.
visit값을 통해 내가 앞으로 나아가야할 곳이 이미 내가 방문했다면 그 위치를 더 방문할 필요가없으니 continue를 한다
그후에는 min을 통해  현재까지 내가 찾은 최솟값과, 지금 내위치에서 다음위치로 갈 비용 + 다음 위치에서 찾은 min 값을 받으므로서  최솟 값을 갱신 해준다

전체 코드는 아래와 같다

#include <iostream>
#include <cstring>
using namespace std;
int n; int dp[16][1 << 16];
int map[16][16];
#define INF 987654321
int dfs(int cur, int visit) {
	if (visit == (1 << n) - 1) {
		if (map[cur][0] == 0) {
			return INF;
		}
		return map[cur][0];
	}

	if (dp[cur][visit] != -1) {
		return dp[cur][visit];
	}

	dp[cur][visit] = INF;

	for (int i = 0; i < n; i++) {
		if (map[cur][i] == 0)
			continue;
		if ((visit & (1 << i)) == (1 << i))
			continue;
		dp[cur][visit] = min(dp[cur][visit], map[cur][i] + dfs(i, visit | (1 << i)));
	}
	return dp[cur][visit];
}
int main() {
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << dfs(0, 1);
}

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

이 문제의 경우 비트 마스킹 문제 였다 정확히는 비트마스킹을 이용한 브루트 포스가 맞다
비트마스킹을 통해 모든 경우의 수에 대해 구한후 푸는 문제였다
각  재료의 사용 여부를 나타내는 표를 한번 그려보겠다

그릴시 이러한 이미지  가  만들어  진다 즉 사용하면 1 사용하지 않으면 0  위에표는 2번 4번을 사용하고 5개의 재료로 만들수 있는 32개의 경우의 수중 10번 조합이라고 보면된다 그이유는 이진수 01010은 10이기 때문이다
여기 까지 구했으면 우리는 각 조합마다의 재료의 합과 비용의 합을 구한다

그 다음 조건을 만족했을 경우 Map 에다가 가격과 해당 가격에 대한 조합들을  저장해준다 그후 만족한 조합의 최소 가격의 map에서 vector에 조합들이 저장되어 있을 것이고 해당 조합을 오름 차순으로 정렬하여 출력해 주면 된다

#include<bitset>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#define INF 200000000
using namespace std;
int n;
map<int, vector<vector<int>>> nutritient_map;
int mp_sum, mf_sum, ms_sum, mv_sum, mc_sum;
int costMax = INF;
struct nutritient {
	int p, f, s, v, c;
};
int main() {
	int mp, mf, ms, mv;
	cin >> n >> mp >> mf >> ms >> mv;
	nutritient arr[15];
	for (int i = 0; i < n; i++) {
		cin >> arr[i].p >> arr[i].f >> arr[i].s >> arr[i].v >> arr[i].c;
	}
	for (int i = 1; i <  (1 << n); i++) {
		mp_sum = mf_sum = ms_sum = mv_sum = mc_sum = 0;
		vector<int> v;
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) {
				mp_sum += arr[j].p;
				mf_sum += arr[j].f;
				ms_sum += arr[j].s;
				mv_sum += arr[j].v;
				mc_sum += arr[j].c;
				v.push_back(j + 1);
			}
		}

		if (mp_sum >= mp && mf_sum >= mf && ms_sum >= ms && mv_sum >= mv) {
			if (costMax >= mc_sum) {
				costMax = mc_sum;
				nutritient_map[costMax].push_back(v);
			}
		}
	}
	if (costMax == INF) {
		cout << -1 << endl;
	}
	else {
		cout << costMax << endl;
		sort(nutritient_map[costMax].begin(), nutritient_map[costMax].end());
		for (int i : nutritient_map[costMax][0]) {
			cout << i << " ";
		}
	}
}

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

이 문제의 경우 그리디와 비트 마스킹  문제이다 처음에는 while문으로 코드를 작성했으나 해당 문제를 해결 하려했으나 실패 했다. 이에 비트  마스킹을 사용해서 문제를 풀어야 함을 깨달았다. 이 문제를 풀기 위한 생각은 

3리터짜리 물병을 생각해 보면 2리터 물병 하나 1리터 물병이 있다고 가정 하자. 얘를  물병 한개짜리를 만드는 방법은 1리터짜리 물병을 하나더해서 2리터짜리를 만든후 4리터 물병을 만드는 방법이다

즉 이문제를 풀기  위해서는 가장 작은 물병들을 계속 그다음 큰 물병들로 만들면서 진행 해야한다 자 대표적인 예로
2번째 테스트 케이스를 예시로 생각해봅시다

이 문제의 경우 0번째  칸에 있는 1리터짜리 물병을 일단 큰물병으로 만들어보자 1+1 해서 2리터로 만든다 그 후 최소 물병과 다른  물병의 갯수를 저장해놓고 일단  계속 가장 작은 물병을 다음 큰 물병으로 변경시켜 가면서 물병을 합치면서 크기를 늘리면서 갯수를 줄이는 로직이다 그후 최소 물병의  갯수를  만족하면 로직진행을 끝내면 된다

#include<bitset>
#include<iostream>
using namespace std;
int main() {
	int n, k;
	int ans=0;
	cin >> n >> k;
	while (true) {
		int temp = n;
		// 현재 1을 못만났다는 의미
		int firstOnidx = -1;
		//  내가  가지고 있는 물병의 갯수
		int cnt=0;
		// 내가 비교하려는 인덱스의 번호
		int idx = 0;
		
		//현재 물병의 수를 세는 로직
		while (temp) {
			if (temp & 1) {
				if (firstOnidx == -1)
					firstOnidx = idx;
				cnt++;
			}
			idx++;
			//다음 번째 인덱스를 비교하기 위해 오른쪽으로 1칸 이동
			temp >>= 1;
		}
		//
		if (cnt <= k) {
			break;
		}
		else {
			//가장 작은 양이 담겨져 있는 물병을 합쳐서 다음  크기의 물병을 만들기 위함 반복하다보면 원래있던 더큰 크기의 물병과 합쳐지면서 크기가 줄어듬
			n += (1 << firstOnidx);
			//산 물병의  갯수 크기2짜리 물병은 1개짜리 물병 2개 합친것
			ans += (1 << firstOnidx);
		}

		
	}
	cout << ans;
}