21년 8월 알고리즘 스터디 5주차

17142 번 : 연구소 3

---

    백트래킹으로 활성화 할 바이러스의 조합을 만들었고, 이를 BFS 로 최소 시간을 구하는 방법으로 풀이했다.

 

#include 
#include 
#include 
#include 

using namespace std;

int N, M, cnt_0, ans;

int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };

vector<vector> map;
vector<vector> visited;
vector<pair<int, int="">> virus, active;

void bfs()
{
	int y, x, time;
	queue<tuple<int, int,="" int="">> q;

	int cnt_copy = cnt_0;

	if (cnt_0 == 0)
	{
		ans = 0;
		return;
	}

	visited.assign(N + 2, vector(N + 2, false));

	for (int i = 0; i < active.size(); ++i)
	{
		q.push({ active[i].first, active[i].second, 0 });
		visited[active[i].first][active[i].second] = true;
	}

	while (!q.empty())
	{
		tie(y, x, time) = q.front();
		q.pop();

		for (int i = 0; i < 4; ++i)
		{
			if (!visited[y + dy[i]][x + dx[i]] && (map[y + dy[i]][x + dx[i]] == 0 || map[y + dy[i]][x + dx[i]] == 2))
			{
				q.push({ y + dy[i], x + dx[i], time + 1 });
				visited[y + dy[i]][x + dx[i]] = true;
				
				if (map[y + dy[i]][x + dx[i]] == 0 && --cnt_copy == 0)
				{
					while (!q.empty())
						q.pop();

					ans = (ans < time + 1) ? ans : time + 1;
				}
			}
		}
	}
}

void active_virus(int n)
{
	if (active.size() == M)
	{
		bfs();
	}

	for (int i = n; i < virus.size(); ++i)
	{
		active.push_back(virus[i]);
		active_virus(i + 1);
		active.pop_back();
	}
}

int main(void)
{
	cin >> N >> M;

	ans = 2501;
	cnt_0 = 0;
	visited.assign(N + 2, vector(N + 2, false));
	map.assign(N + 2, vector(N + 2, 1));

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

			if (map[i][j] == 0)
			{
				++cnt_0;
			}

			else if (map[i][j] == 2)
			{
				virus.push_back({ i,j });
			}
		}
	}

	active_virus(0);

	if (ans == 2501)
		cout << "-1\n";

	else
		cout << ans << '\n';
}

// 시간 적게 쓰인 소스 : https://www.acmicpc.net/source/32833118
// 분석해 볼 소스 : https://www.acmicpc.net/source/32303370</tuple<int,></pair<int,></vector</vector

 

 

1495 번 : 기타리스트

---

    DP 를 이용해서 마지막 곡 볼륨의 최댓값을 구했다.

 

#include 
#include 

using namespace std;

int N, S, M;
vector vol_diff;
vector<vector> cache;

int dp(int pos, int P)
{
	if (pos == N)
		return P;

	if (cache[pos][P] != -11)
		return cache[pos][P];

	int max_vol = -1;

	if (P + vol_diff[pos] <= M)
		max_vol = dp(pos + 1, P + vol_diff[pos]);

	if (P - vol_diff[pos] >= 0)
		max_vol = ((M - max_vol) < (M - dp(pos + 1, P - vol_diff[pos]))) ? max_vol : dp(pos + 1, P - vol_diff[pos]);

	return cache[pos][P] = max_vol;
}

int main(void)
{
	cin >> N >> S >> M;

	vol_diff.assign(N + 1, 0);
	cache.assign(N + 1, vector(M+1, -11));

	for (int i = 0; i < N; ++i)
	{
		cin >> vol_diff[i];
	}

	cout << dp(0, S) << '\n';
}

// 깔끔하게 구현한 소스 : https://www.acmicpc.net/source/31948482</vector

 

 

8980 번 : 택배

---

    거리가 짧은 것부터 고려하면 최대 박스의 수를 구할 수 있을 거라고 생각해서 구현했다. 배송 스케줄에 이동 거리가 짧은 것부터 배치해서 최대 박스의 수를 구하도록 구현했는데, 배송이 겹칠 때 추가로 배송 가능한 상자의 개수를 구하는 알고리즘에 문제가 있어 부분 성공만 받았다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

int N, C, M, ans;

vector<vector<int>> goods;
vector<tuple<int, int, int, int>> info;

void print()
{
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			cout << goods[i][j] << ' ';
		}
		cout << '\n';
	}
}

int main(void)
{
	// vol : 그 구간에서 배송 중인 박스의 가능한
	int dis, from, to, cnt, vol, tmp;

	cin >> N >> C >> M;
	
	ans = 0;
	goods.assign(N + 1, vector<int>(N + 1, 0));

	while (M--)
	{
		cin >> from >> to >> cnt;
		info.push_back({ to - from, from, to, cnt });
	}

	sort(info.begin(), info.end());

	for (int i = 0; i < info.size(); ++i)
	{
		print();

		if (i == 5)
		{
			i = 5;
		}

		tie(dis, from, to, cnt) = info[i];

		cout << from << ' ' << to << '\n';

		vol = 0;

		for (int j = to; j > from; --j)
		{
			tmp = 0;

			for (int k = 1; k <= N; ++k)
			{
				tmp = (tmp > goods[k][j]) ? tmp : goods[k][j];
			}

			vol += tmp;
		}

		vol = C - vol;

		if (vol < 0)
			vol = 0;

		goods[from][to] = (vol < cnt) ? vol : cnt;

		ans += goods[from][to];
	}

	cout << ans << '\n';
}

 

 

10164 번 : 격자상의 경로

---

    통과 여부와 좌표 값을 저장하여 DP 로 풀이했다.

 

#include 
#include 

using namespace std;

vector<vector> cache;

int N, M, K;

int dp(bool isPass, int coor)
{
	if (coor > N * M || (!isPass && K < coor))
		return 0;

	else if (coor == N * M)
	{
		if (isPass)
			return 1;

		else
			return 0;
	}

	int cnt = 0;

	if (cache[isPass][coor] != -1)
		return cache[isPass][coor];

	isPass = isPass || (coor == K);

	if (coor % M != 0)
		cnt += dp(isPass, coor + 1);

	cnt += dp(isPass, coor + M);

	return cache[isPass][coor] = cnt;
}

int main(void)
{
	cin >> N >> M >> K;
	
	cache.assign(2, vector((N + 1) * (M + 1), -1));

	if(K == 0)
		cout << dp(true, 1) << '\n';

	else
		cout << dp(false, 1) << '\n';
}

// 좋은 소스 : https://www.acmicpc.net/source/31397007
// 소스 분석 : https://www.acmicpc.net/source/30952429</vector

 

 

1013 번 : Contact

---

    패턴이 성립하는 경우에만 다음 인덱스로 넘어갈 수 있도록 했고, 이를 통해 모든 경우를 확인하도록 구현했다.

 

#include 
#include 
#include 

using namespace std;

string input;
bool isMatch;

void check(int pos)
{
	if (isMatch)
	{
		return;
	}

	if (pos == input.size())
	{
		cout << "YES\n";
		isMatch = true;
	}

	int tmp = pos;
	bool isEnd = false;

	if (pos < input.size() - 3 && input.substr(pos, 3) == "100")
	{
		tmp += 3;

		while (tmp < input.size())
		{
			if (input[tmp] == '0')
			{
				++tmp;
			}

			else
				break;
		}

		while (tmp < input.size())
		{
			if (input[tmp] == '1')
			{
				// 전의 조건을 만족했다면 언제든 새로운 패턴이 나올 수 있음.
				if (isEnd)
				{
					check(tmp);
				}

				++tmp;
				isEnd = true;
			}

			else
				break;
		}

		if (isEnd)
			check(tmp);
	}

	if (pos < input.size() - 1 && input.substr(pos, 2) == "01")
		check(pos+2);
}

int main(void)
{
	int n;

	cin >> n;

	while (n--)
	{
		cin >> input;

		isMatch = false;

		check(0);

		if (!isMatch)
			cout << "NO\n";
	}
}

// 좋은 소스 : https://www.acmicpc.net/source/32973010

 

 

1600 번 : 말이 되고픈 원숭이

---

    좌표와 점프 횟수를 큐에 push 하도록 구현하여 BFS 로 풀이했다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int K, W, H;

int knight_dx[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int knight_dy[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };

int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };

vector<vector<int>> map;
vector<vector<vector<bool>>> visited;

int main(void)
{
	int ans = -1;
	int y, x, jump, time;

	cin >> K >> W >> H;

	map.assign(H + 1, vector<int>(W + 1, 1));
	visited.assign(H + 1, vector<vector<bool>>(W + 1, vector<bool>(K + 1, false)));

	for (int i = 1; i <= H; ++i)
	{
		for (int j = 1; j <= W; ++j)
		{
			cin >> map[i][j];
		}
	}

	queue<tuple<int, int, int, int>> q;

	q.push({ 1, 1, 0, 0 });
	visited[1][1][0] = true;

	while (!q.empty())
	{
		tie(y, x, jump, time) = q.front();
		q.pop();

		if (y == H && x == W)
		{
			ans = time;
			break;
		}

		if (jump < K)
		{
			for (int i = 0; i < 8; ++i)
			{
				if (y + knight_dy[i] < 1 || y + knight_dy[i] > H || x + knight_dx[i] < 1 || x + knight_dx[i] > W)
				{
					continue;
				}

				if (!visited[y + knight_dy[i]][x + knight_dx[i]][jump+1] && map[y + knight_dy[i]][x + knight_dx[i]] != 1)
				{
					visited[y + knight_dy[i]][x + knight_dx[i]][jump+1] = true;
					q.push({ y + knight_dy[i], x + knight_dx[i], jump + 1, time + 1});
				}
			}
		}

		for (int i = 0; i < 4; ++i)
		{
			if (y + dy[i] < 1 || y + dy[i] > H || x + dx[i] < 1 || x + dx[i] > W)
			{
				continue;
			}

			if (!visited[y + dy[i]][x + dx[i]][jump] && map[y + dy[i]][x + dx[i]] != 1)
			{
				visited[y + dy[i]][x + dx[i]][jump] = true;
				q.push({ y + dy[i], x + dx[i], jump, time + 1});
			}
		}
	}

	
	cout << ans << '\n';
}

//canJump 라는 boolean 변수로 visited 으로 점프할 수 있는지만 확인했는데, jump 횟수가 적은게 후에 도달할 수도 있으니 jump 가능 여부가 아닌 jump 횟수로 확인했다.

 

 

5639 번 : 이진 검색 트리

---

    구조체를 이용하여 노드를 구현했고, 전위 순회 결과를 통해 트리를 구성한 뒤, 이를 통해 후위 순회 결과를 출력했다.

 

#include 

using namespace std;

struct Node
{
	int num;
	
	Node* left;
	Node* right;
};

Node* push(Node* node, int num)
{
	if (node == NULL)
	{
		node = new Node();
		node->num = num;
		node->left = NULL;
		node->right = NULL;
	}

	else
	{
		if (num < node->num)
		{
			node->left = push(node->left, num);
		}

		else
		{
			node->right = push(node->right, num);
		}
	}

	return node;
}

void postorder(Node* node)
{
	if (node->left != NULL)
		postorder(node->left);

	if (node->right != NULL)
		postorder(node->right);

	cout << node->num << '\n';
}

int main(void)
{
	int input;

	Node* root = NULL;

	while (cin >> input)
	{
		root = push(root, input);
	}

	postorder(root);
}

// 좋은 코드 참조 : https://www.acmicpc.net/source/32954636