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

16234 번 : 인구 이동

---

    BFS 로 연합의 인구 수의 합을 구한 후, 칸의 개수로 나누어 평균 인구 수를 구했다. BFS 로 연결된 칸을 확인하며 A_union 에 위치를 저장한 뒤 평균 인구 수를 구한 후 A_union 내의 모든 값을 평균 인구 수로 대체했다. 이렇게 모든 칸이 조건을 충족하지 않을 때까지 반복하여 답을 구했다.

 

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

using namespace std;

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

vector<vector<int>> A;
vector<vector<bool>> visited;
queue<pair<int,int>> A_union;

int bfs(int x, int y)
{
	int cnt = 1, total = 0;
	queue<pair<int, int>> q;

	if (!visited[x][y])
	{
		q.push({ x, y });
		A_union.push({ x, y });
		total = A[x][y];
		visited[x][y] = true;

		while (!q.empty())
		{
			pair<int, int> here = q.front();
			q.pop();

			for (int k = 0; k < 4; ++k)
			{
				if (here.first + dx[k] < 0 || here.first + dx[k] == N || here.second + dy[k] < 0 || here.second + dy[k] == N || visited[here.first + dx[k]][here.second + dy[k]])
					continue;

				if (abs(A[here.first][here.second] - A[here.first + dx[k]][here.second + dy[k]]) >= L && abs(A[here.first][here.second] - A[here.first + dx[k]][here.second + dy[k]]) <= R)
				{
					q.push({ here.first + dx[k], here.second + dy[k] });
					A_union.push({ here.first + dx[k], here.second + dy[k] });
					visited[here.first + dx[k]][here.second + dy[k]] = true;
					++cnt;
					total += A[here.first + dx[k]][here.second + dy[k]];
				}
			}
		}
	}

	return total/cnt;
}

int main(void)
{
	int ans = -1, ave = -1, check = 0;

	cin >> N >> L >> R;

	A.assign(N, vector<int>(N, 0));

	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			cin >> A[i][j];

	while (check != N*N)
	{
		++ans;
		check = 0;
		visited.assign(N, vector<bool>(N, false));

		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				ave = bfs(i, j);

				while (!A_union.empty())
				{
					pair<int, int> pos = A_union.front();
					A_union.pop();

					A[pos.first][pos.second] = ave;
				}

				if (ave == A[i][j])
				{
					++check;
					continue;
				}
			}
		}
	}

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

 

 

10973 번 : 이전 순열

---

    순열이 주어질 때, 마지막 값부터 앞의 값과 비교하며 자신보다 크면 위치를 바꾼 뒤, 바꾼 위치 뒷부분을 내림차순으로 정렬하는 방식으로 구현하려고 했다. 구현 도중 prev_permutation, next_permutation 함수를 알게 돼서 해당 함수로 해결했다.

 

// WA 받은 코드
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void)
{
	vector<int> seq, swap_std;
	int N, i, j, swap_pos, max_pos;
	bool flag = true;

	cin >> N;
	seq.assign(N, 0);

	for (i = 0; i < N; ++i)
		cin >> seq[i];

	swap_pos = 0;
	swap_std.push_back(N - 1);

	for (i = 0; i < swap_std.size(); ++i)
	{
		//swap_pos : 바꿀 작은 수 + 바꿀 큰 수 * 100000
		//swap_std : 비교할 수의 목록
		for (j = swap_std[i] - 1; j >= swap_pos%100000; --j)
		{
			if (seq[j] > seq[swap_std[i]])
			{
				swap_pos = j+i*100000;
				flag = false;
				break;
			}

			else
				if (swap_std[i] == N - 1 || swap_std[i] != 0)
					swap_std.push_back(j);
		}
	}

	if (flag)
		cout << "-1";

	else
	{
		//가능한 후열에서 바꿀 수 있도록 swap
		swap(seq[swap_std[swap_pos / 100000]], seq[swap_pos % 100000]);

		// 내림차순 정렬
		for (i = swap_pos%100000 + 1; i < N; ++i)
		{
			max_pos = N-1;

			for (j = i; j < N; ++j)
			{
				if (seq[max_pos] < seq[j])
					max_pos = j;
			}

			swap(seq[i], seq[max_pos]);
		}

		for (i = 0; i < N; ++i)
			cout << seq[i] << ' ';
	}
}

// AC 받은 코드
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void)
{
	int n;
	bool flag = false;

	cin >> n;

	vector<int> seq(n);

	cin >> seq[0];

	for (int i = 1; i < n; ++i)
	{
		cin >> seq[i];

		if (seq[i - 1] > seq[i])
			flag = true;
	}

	if (flag)
	{
		prev_permutation(seq.begin(), seq.end());

		for (auto& i : seq)
			cout << i << ' ';
	}

	else
		cout << "-1";
}

 

 

2011 번 : 암호코드

---

    DP 로 모든 경우를 탐색해 경우의 수를 구했다.

 

#include <iostream>
#include <string>

using namespace std;

bool flag;
string pw;
int cache[5001];

int dp(int n)
{
	int cnt = 0;
	string pw_part;

	if (n == pw.length())
		return 1;

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

	if (pw[n] != '0')
	{
		cnt += dp(n + 1);

		if (n < pw.length() - 1)
		{
			pw_part = pw.substr(n, 2);

			if (stoi(pw_part) > 0 && stoi(pw_part) < 27)
				cnt += dp(n + 2);

			else if (stoi(pw_part) % 10 == 0)
				flag = false;
		}
	}

	else
		return 0;

	return cache[n] = cnt % 1000000;
}

int main(void)
{
	cin >> pw;

	flag = true;
	fill_n(cache, pw.length(), -1);

	dp(0);

	if (!flag)
		cout << "0\n";

	else
		cout << dp(0)<<'\n';
}

 

 

1325 번 : 효율적인 해킹

---

    DFS 를 사용하여 연결된 컴퓨터의 개수를 구한 후, 그 값을 max_com vector 에 push 했다. 모든 컴퓨터에 대해 DFS 가 이루어졌다면 max_com 을 내림차순으로 정렬한 뒤 가장 큰 값을 가지는 컴퓨터 번호들을 출력했다.

 

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

using namespace std;

int N, M, host, trust, cnt;
bool visited[10001];

vector<vector<int>> adj(10001);
vector<int> ans;
vector<pair<int, int>> max_com;

void dfs(int vertex)
{
	++cnt;
	visited[vertex] = true;

	for (int i = 0; i < adj[vertex].size(); ++i)
		if (!visited[adj[vertex][i]])
			dfs(adj[vertex][i]);
}

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

	for (int i = 0; i < M; ++i)
	{
		cin >> trust >> host;

		adj[host].push_back(trust);
	}

	for (int i = 1; i <= N; ++i)
	{
		cnt = 0;
		
		for (int i = 0; i <= N; ++i)
			visited[i] = false;

		dfs(i);

		max_com.push_back({ cnt, i });
	}

	sort(max_com.begin(), max_com.end(), greater<>());

	for (int i = 0; i < max_com.size(); ++i)
		if (max_com[i].first == max_com[0].first)
			ans.push_back(max_com[i].second);

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

	for (int i = 0; i < ans.size(); ++i)
		cout << ans[i] << ' ';
}

 

 

2573 번 : 빙산

---

    dfsall 함수에서 모든 빙산에 대해 dfs 를 실행하여 덩어리의 개수를 구했고, meltdown 함수를 통해 빙산의 높이가 줄였다. dfsall 함수의 반환 값이 1 초과가 되면 2 덩어리 이상으로 분리된 것으로 판단하여 while 문 수행 횟수를 출력했다.

 

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<vector<int>> field, melt;
vector<vector<bool>> visited;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };

void meltdown(void)
{
	int cnt;

	for (int i = 1; i < N-1; ++i)
	{
		for (int j = 1; j < M-1; ++j)
		{
			cnt = 0;

			for (int k = 0; k < 4; ++k)
			{
				if (field[i + dy[k]][j + dx[k]] == 0)
					++cnt;
			}

			melt[i][j] -= cnt;

			if (melt[i][j] < 0)
				melt[i][j] = 0;
		}
	}
}

void dfs(int y, int x)
{
	visited[y][x] = true;

	for (int k = 0; k < 4; ++k)
	{
		if (!visited[y + dy[k]][x + dx[k]] && field[y + dy[k]][x + dx[k]] != 0)
		{
			dfs(y + dy[k], x + dx[k]);
		}
	}
}

int dfsAll()
{
	int frac = 0;

	visited.assign(N, vector<bool>(M, false));

	for (int i = 1; i < N-1; ++i)
	{
		for (int j = 1; j < M-1; ++j)
		{
			if (!visited[i][j] && field[i][j] != 0)
			{
				dfs(i, j);
				++frac;
			}
		}
	}

	return frac;
}

int main(void)
{
	int ans = 0;
	cin >> N >> M;

	field.assign(N, vector<int>(M, 0));

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

	while (dfsAll()==1)
	{
		melt = field;

		meltdown();

		field = melt;

		++ans;
	}

	if (dfsAll() > 1)
		cout << ans << '\n';

	else
		cout << "0\n";
}

 

 

15903 번 : 카드 합체 놀이

---

    가장 작은 수 2개를 선택해야 가장 작은 점수를 얻을 수 있다. 따라서 우선순위 큐를 이용하여 가장 작은 수 2개를 찾았고, 그 값으로 점수를 계산하여 출력했다.

 

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
	int n, m, input;
	long long c1, c2, ans = 0;
	priority_queue<long long, vector<long long>, greater<long long>> card;

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> input;
		card.push(input);
	}

	for (int i = 0; i < m; ++i)
	{
		c1 = card.top();
		card.pop();
		c2 = card.top();
		card.pop();

		card.push(c1 + c2);
		card.push(c1 + c2);
	}

	while (!card.empty())
	{
		ans += card.top();
		card.pop();
	}

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