굳건하게

문제 : https://www.acmicpc.net/problem/16637

[ 알고리즘풀이 ]

■ 우리는 (N / 2) 개의 연산과 (N / 2) + 1 개의 숫자로 이루어진 식을 입력받는다. 또, 1, 3, 5, 7 ⋯ 과 같이 홀수 인덱스는 연산, 짝수 인덱스는 숫자에 해당한다.

■ N / 2 개의 연산 중 어느 곳에 괄호를 칠지 Backtracking 을 통해 모든 경우에 대해서 식을 계산해본다.

( 이때, 괄호를 친 연산 바로 다음 연산은 괄호가 겹치므로 괄호를 check 하면 안된다. )

■ 식을 앞에서부터 순회하며 괄호 유무에 따라 식을 숫자 파트와 연산 파트로 나눠서 vector 에 저장한다.

- 숫자와 숫자 다음 칸인 연산에 괄호가 쳐져있다면 그 다음 숫자와 먼저 계산을 하고 계산한 값과 그 다음 연산을 vector에 저장한다.

- 그렇지 않다면, 해당 숫자과 연산을 각각 vector에 저장한다.

■ 저장된 숫자와 연산을 계산한다.

■ 답을 갱신한다.

■ 답은 최대 9^10 으로 long long 으로 저장해줘야한다..!!!

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;

int N;
long long ans = -999999999999999;
string expression;
bool op[9] = {};

long long getResult(void) {
	vector<long long> v1;
	vector<char> v2;
	int i = 0;
	while(i < N){
		if (op[(i + 1) / 2]) {// 숫잔데 괄호쳐져있음.
			if (expression[i + 1] == '+')
				v1.push_back((expression[i] - '0') + (expression[i + 2] - '0'));
			else if (expression[i + 1] == '-')
				v1.push_back((expression[i] - '0') - (expression[i + 2] - '0'));
			else if (expression[i + 1] == '*')
				v1.push_back((expression[i] - '0') * (expression[i + 2] - '0'));

			if (i + 3 < N)
				v2.push_back(expression[i + 3]);
			i += 4;
		}
		else if (!op[(i + 1) / 2]){
			v1.push_back(expression[i] - '0');
			if(i + 1 < N)
				v2.push_back(expression[i + 1]);
			i += 2;
		}
	}
	long long sum = v1[0];
	for (int i = 1; i < v1.size(); i++) {
		if (v2[i - 1] == '+')
			sum += v1[i];
		else if (v2[i - 1] == '-')
			sum -= v1[i];
		else if (v2[i - 1] == '*')
			sum *= v1[i];
	}
	return sum;
}

void Backtracking(int start) {
	ans = max(ans, getResult());
	for (int i = start; i < N / 2; i++) {
		op[i] = 1;
		Backtracking(i + 2);
		op[i] = 0;
	}
	return;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> expression;

	Backtracking(0);

	cout << ans;
}

문제 : https://www.acmicpc.net/problem/17779

[ 알고리즘풀이 ]

■ 처음엔 5번 선거구를 먼저 정하고, 남는 자리에 한해서 아래를 만족하면 1, 2, 3, 4번 선거구로 정하려고 했다. 그러면 5번 선거구만 정하고 나머지는 전체를 순회하며 단순 if 문 만으로 처리할 수 있기 때문에 구현이 깔끔할 것 같았다.

• 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y

• 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N

• 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2

• 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

하지만, 5번 선거구를 먼저 선정하려면 다이아몬드를 그려야되는데 이 부분이 구현하기 어려워, 결국 1, 2, 3, 4 번 선거구를 정하고 남는 부분을 5번 선거구로 정했다.

■ 모든 x, y, d1, d2에 대해서 게임을 진행하고, 애초에 5개 구역으로 못나누는 경우는 return, 아니라면 선거구를 나누며 답을 갱신하면 된다.

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

int N, map[21][21] = {}, ans = INF;

void separate(int x, int y, int d1, int d2) {
	// 애초에 5개 구역으로 못나누는 경우.
	if (!(1 <= x && x + d1 + d2 <= N && 1 <= y - d1 && y + d2 <= N))
		return;

	int label[21][21] = {}, sum[5] = {};
	// 1구역
	for (int r = 1; r < x + d1; r++) {
		if (r < x)
			for (int c = 1; c <= y; c++)
				label[r][c] = 1;
		else
			for (int c = 1; c <= y - (r - x + 1); c++)
				label[r][c] = 1;
	}
	// 2구역
	for (int r = 1; r <= x + d2; r++) {
		if (r <= x)
			for (int c = y + 1; c <= N; c++)
				label[r][c] = 2;
		else
			for (int c = y + 1 + (r - x); c <= N; c++)
				label[r][c] = 2;
	}
	// 3구역
	for (int r = x + d1; r <= N; r++) {
		if (r < x + d1 + d2)
			for (int c = 1; c < y - d1 + (r - (x + d1)); c++)
				label[r][c] = 3;
		else
			for (int c = 1; c < y - d1 + d2; c++)
				label[r][c] = 3;
	}
	// 4구역
	for (int r = x + d2 + 1; r <= N; r++) {
		if (r <= x + d1 + d2)
			for (int c = y + d2 + 1 - (r - (x + d2)); c <= N; c++)
				label[r][c] = 4;
		else
			for (int c = y - d1 + d2; c <= N; c++)
				label[r][c] = 4;
	}
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			sum[label[r][c]] += map[r][c];

	sort(sum, sum + 5);
	ans = min(ans, sum[4] - sum[0]);
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];

	
	// d1, d2, x, y 마다 게임을 진행하자.
	for (int d1 = 1; d1 <= N; d1++)
		for (int d2 = 1; d2 <= N; d2++)
			for (int x = 1; x <= N; x++)
				for (int y = 1; y <= N; y++)
					separate(x, y, d1, d2);
	
	cout << ans;
}

문제 : https://www.acmicpc.net/problem/17142

기존풀이 :  https://travelbeeee.tistory.com/332

[ 알고리즘풀이 ]

■ 연구소의 사이즈는 N, 바이러스의 개수는 M ( map을 입력받으면서 '0' 인 공간을 미리 count 해둔다. )

■ 바이러스를 M개 뽑아서 감염을 확산시킬 것이므로, 바이러스의 위치를 vir 에 저장한다.

■ Backtracking 을 이용해 vir에 저장된 바이러스 중 M개를 뽑는다.

■ 뽑힌 M개의 바이러스를 BFS 탐색을 이용해 감염을 확산시킨다. ( '0' 인 공간을 탐색하면 count )

 이때, 탐색을 하면서 Time 을 count 해주고, 앞으로 밟아야 하는 땅이 '0' 이라면, realTime을 Time 값으로 갱신해준다.

 기존의 코드는 현재 밟은 땅들이 모두 '2' 이고, 앞으로 탐색할 곳이 없을 때를 찾기 위해 bool check1, check2를 이용했다. 이 부분을 조금 더 간결하게 코딩하기 위해 실제로 내가 탐색하는데 필요한 realTime 과 그냥 탐색이 진행될 때마다 시간을 count 해주는 Time 변수 두 개를 이용했다. 코드가 실제로 눈에 띄게 짧아진 것은 아니지만 가독성 면에서 조금 더 간결한 코드이지않을까 싶다...!

■ BFS 탐색을 하며 count 한 값과 (1) 에서 count 한 값을 비교해 모든 지역에 감염이 진행되었다면, realTime과 답을 비교해 답을 갱신한다.

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#define INF 987654321

using namespace std;

vector<pair<int, int>> vir;
int N, M, spaceCount, ans = INF, map[50][50], dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
bool choice[10];

void spreadVirus(void) {
	bool visited[50][50] = {};
	queue<pair<int, int>> q;
	for (int i = 0; i < vir.size(); i++)
		if (choice[i]) {
			q.push({ vir[i].first, vir[i].second });
			visited[vir[i].first][vir[i].second] = 1;
		}

	int realTime = 0, time = 0, cnt = 0;
	while (!q.empty()) {
		int s = q.size();
		for (int i = 0; i < s; i++) {
			pair<int, int> cur = q.front();
			q.pop();
			for (int j = 0; j < 4; j++) {
				int nextX = cur.first + dx[j], nextY = cur.second + dy[j];
				if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N) {
					if (map[nextX][nextY] != 1 && !visited[nextX][nextY]) {
						visited[nextX][nextY] = 1;
						q.push({ nextX, nextY });
						if (map[nextX][nextY] == 0) {
							cnt++;
							realTime = time + 1;
						}
					}
				}
			}
		}
		time++;
	}

	if (cnt == spaceCount)
		ans = min(ans, realTime);

	return;
}

void Backtracking(int s, int cnt) {
	if (cnt == M) {
		spreadVirus();
		return;
	}
	for (int i = s; i < vir.size(); i++) {
		choice[i] = true;
		Backtracking(i + 1, cnt + 1);
		choice[i] = false;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0)
				spaceCount++;
			if (map[i][j] == 2)
				vir.push_back({ i, j });
		}
	}

	Backtracking(0, 0);

	(ans == INF) ? cout << -1 : cout << ans;
}

문제 : https://www.acmicpc.net/problem/17141

[ 알고리즘풀이 ]

■ 연구소의 사이즈는 N, 바이러스의 개수는 M ( map을 입력받으면서 '0' 인 공간을 미리 count 해둔다. )

■ 바이러스를 M개 뽑아서 감염을 확산시킬 것이므로, 바이러스의 위치를 vir 에 저장한다.

■ Backtracking 을 이용해 vir에 저장된 바이러스 중 M개를 뽑는다.

■ 뽑힌 M개의 바이러스를 BFS 탐색을 이용해 감염을 확산시킨다. ( '0' 인 공간을 탐색하면 count )

    '1' (벽) 이 아니라면 탐색을 진행하면 된다.

■ BFS 탐색을 하며 count 한 값과 (1) 에서 count 한 값을 비교해 모든 지역에 감염이 진행되었다면, 답을 갱신한다.

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#define INF 987654321

using namespace std;

vector<pair<int, int>> vir;
int N, M, spaceCount, ans = INF, map[50][50], dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
bool choice[10];

void spreadVirus(void) {
	bool visited[50][50] = {};
	queue<pair<int, int>> q;
	for (int i = 0; i < vir.size(); i++)
		if (choice[i]){
			q.push({ vir[i].first, vir[i].second });
			visited[vir[i].first][vir[i].second] = 1;
		}
	int time = -1, cnt = 0;
	while (!q.empty()) {
		int s = q.size();
		for (int i = 0; i < s; i++) {
			pair<int, int> cur = q.front();
			q.pop();
			for (int j = 0; j < 4; j++) {
				int nextX = cur.first + dx[j], nextY = cur.second + dy[j];
				if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N) {
					if (map[nextX][nextY] != 1 && !visited[nextX][nextY]) {
						visited[nextX][nextY] = 1;
						q.push({ nextX, nextY });
						if (map[nextX][nextY] == 0)
							cnt++;
					}
				}
			}
		}
		time++;
	}
	if (cnt == spaceCount)
		ans = min(ans, time);
	return;
}

void Backtracking(int s, int cnt) {
	if (cnt == M) {
		spreadVirus();
		return;
	}
	for (int i = s; i < vir.size(); i++) {
		choice[i] = true;
		Backtracking(i + 1, cnt + 1);
		choice[i] = false;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0)
				spaceCount++;
			if (map[i][j] == 2)
				vir.push_back({ i, j });
		}
	}

	Backtracking(0, 0);

	(ans == INF) ? cout << -1 : cout << ans;
}