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

5567 번 : 결혼식

---

    Queue 에 { 노드 번호, 1 번 노드와의 거리 } 를 넣어서 BFS 로 탐색하도록 구현했다.

 

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

using namespace std;

int n, m, a, b;
vector<vector<int>> relation;
vector<bool> visited;

int main(void)
{
	int ans = 0;
	queue<pair<int, int>> q;

	cin >> n >> m;

	relation.assign(n + 1, vector<int>());
	visited.assign(n + 1, false);

	for (int i = 0; i < m; ++i)
	{
		cin >> a >> b;
		relation[a].push_back(b);
		relation[b].push_back(a);
	}

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

	while (!q.empty())
	{
		int here = q.front().first;
		int bridge = q.front().second;

		q.pop();

		if (bridge > 2)
			break;

		++ans;

		for (int i = 0; i < relation[here].size(); ++i)
		{
			if (!visited[relation[here][i]])
			{
				q.push({ relation[here][i], bridge + 1 });
				visited[relation[here][i]] = true;
			}
		}
	}

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

 

 

16235 번 : 나무 제테크

---

    처음에는 vector 로만 구현했었는데 반복문 내에서 sort 함수를 계속 쓰다 보니 시간 초과가 나왔다. 모든 나무에 대해 pop을 한 뒤 계절에 따른 변화를 적용하고 다시 push 해주는 방식으로 구현하면 sort 함수를 사용하지 않아도 구현이 가능할 것 같았다. 따라서 이에 적합한 deque 자료구조를 통해 구현했다.

 

    처음에 구현하고 테스트 케이스를 확인해봤을 때 계속 잘못된 값이 나와 어려워했다. 실수가 생기는 이유는 반복문 내에서 조건식에 사용되는 변수의 값을 변경했는데 이에 대해 크게 신경 쓰지 않아서 반복문이 엉킨 것이었다. 되는대로 구현하기보다는 생각하고 구현하는 습관을 길러야겠다. 앞으로 코딩을 하면서 코드가 제대로 동작하지 않는다면 배열의 인덱스와 반복문 조건식을 확인해보는 것도 괜찮을 것 같다.

 

    그리고 문제를 똑바로 읽고 조건을 제대로 파악하는 게 무엇보다 중요하다는 것을 다시 한번 깨닫는다. 가장 처음에 모든 칸에 5만큼의 양분이 있다는 조건을 읽지 않고 구현해서 잘못된 부분을 찾느라 고생했다.

 

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

using namespace std;

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

	int N, M, K, x, y, age, size, it;

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

	vector<vector<int>> A, field;
    // tree_data : 현재 살아있는 나무의 데이터를 저장하는 덱
    // tree_death : 올해 죽은 나무의 데이터를 저장하는 덱
	deque<tuple<int, int, int>> tree_data, tree_death;

	cin >> N >> M >> K;

	A.assign(N + 1, vector<int>(N + 1, 0));
	field.assign(N + 1, vector<int>(N + 1, 5));

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

	for (int i = 0; i < M; ++i)
	{
		cin >> x >> y >> age;
		tree_data.push_back({ age, x, y });
	}

	while (K-- && !tree_data.empty())
	{
		size = tree_data.size();

		while(size--)
		{
			tie(age, x, y) = tree_data[0];
			tree_data.pop_front();

			if (field[x][y] >= age)
			{
				field[x][y] -= age;
				++age;
				tree_data.push_back({ age, x, y});
			}

			else
			{
				tree_death.push_back({ age, x, y });
			}
		}

		while(!tree_death.empty())
		{
			tie(age, x, y) = tree_death[0];
			tree_death.pop_front();

			field[x][y] += age / 2;
		}

		size = tree_data.size();
		it = 0;

		while(size--)
		{
			tie(age, x, y) = tree_data[it++];

			if (age % 5 == 0)
			{
				for (int k = 0; k < 8; ++k)
				{
					if (y + dy[k] == 0 || y + dy[k] == N + 1 || x + dx[k] == 0 || x + dx[k] == N + 1)
						continue;

					tree_data.push_front({ 1, x + dx[k], y + dy[k] });
					++it;
				}
			}
		}

		for (int i = 1; i <= N; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				field[i][j] += A[i][j];
			}
		}
	}

	cout << tree_data.size() << '\n';
}

 

 

11066 번 : 파일 합치기

---

    '합친다'라는 개념에 초점을 맞춰 합칠 범위에 따른 최소 비용을 cache 에 저장하여 DP 로 풀었다. 이 문제의 경우 어차피 끝에 가서는 다 합쳐지기에 장의 수를 저장한 수열의 순서는 신경 쓰지 않아도 되는데 수열의 순서에 집중하여 cache 를 어떻게 구성할지 고민하는데 시간을 많이 썼다. 별 의미 없다는 걸 깨달은 뒤에는 큰 어려움 없이 구현할 수 있었다.

 

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

using namespace std;

int T, K;

vector<int> file, sum;
vector<vector<int>> cache;

int dp(int s, int e)
{
	if (s == e)
		return file[s];

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

	int ans = 100000000;
	int part_sum = sum[e];

	if (s != 0)
		part_sum -= sum[s - 1];

	for (int i = s; i < e; ++i)
	{
		ans = min(ans, part_sum + dp(s, i) + dp(i + 1, e));
	}

	return cache[s][e] = ans;
}

int main(void)
{
	cin >> T;

	while (T--)
	{
		cin >> K;

		file.assign(K, 0);
		sum.assign(K, 0);
		cache.assign(K, vector<int>(K, -1));

		cin >> file[0];
		sum[0] = file[0];

		for (int i = 1; i < K; ++i)
		{
			cin >> file[i];
			sum[i] = sum[i - 1] + file[i];
		}

		cout << dp(0, K-1) - sum[K-1] << '\n';
	}
}

 

 

5054 번 : 스타트링크

---

    이 문제도 간단하게 BFS 를 통해 해결할 수 있다. 다만 이 문제도 조건을 제대로 이해하지 못해서 고생했다. 입력으로 주어진 출발점 S 와 도착점 G 가 같을 경우 엘리베이터를 이용할 필요가 없으니 "use the stairs" 를 출력하도록 구현했는데 그냥 0을 출력하면 되는 문제였다. 문제를 제대로 이해한 뒤에 구현하는 습관을 기르자.

 

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
	int F, S, G, U, D, ans = -1, cnt = 0;

	queue<pair<int, int>> q;
	vector<bool> visited;

	cin >> F >> S >> G >> U >> D;

	visited.assign(F + 1, false);

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

	while (!q.empty())
	{
		int here = q.front().first;
		int cnt = q.front().second;

		if (here == G)
		{
			ans = cnt;
			break;
		}
		
		q.pop();

		if (here + U <= F && !visited[here + U])
		{
			q.push({ here + U, cnt + 1 });
			visited[here + U] = true;
		}

		if (here - D >= 1 && !visited[here - D])
		{
			q.push({ here - D, cnt + 1 });
			visited[here - D] = true;
		}
	}

	if (ans == -1)
		cout << "use the stairs\n";

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

 

 

14716 번 : 현수막

---

    DFS 를 몇 번 호출해야 되는지 계산해서 글자의 개수를 파악하도록 구현했다.

 

#include <iostream>
#include <vector>

using namespace std;

int M, N;
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { 1,1,0,-1,-1,-1,0,1 };

vector<vector<int>> banner;
vector<vector<bool>> visited;

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

	for (int k = 0; k < 8; ++k)
	{
		if (y + dy[k] < 0 || y + dy[k] == M || x + dx[k] < 0 || x + dx[k] == N)
			continue;

		if (banner[y + dy[k]][x + dx[k]] == 1 && !visited[y + dy[k]][x + dx[k]])
			dfs(y + dy[k], x + dx[k]);
	}
}

int dfsAll()
{
	int ans = 0;

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

	return ans;
}

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

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

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

	cout << dfsAll() << '\n';
}

 

 

15655 번 : N과 M (6)

---

    입력으로 주어진 수열을 sort 함수를 통해 정렬한 후 재귀를 통해 답을 출력하도록 구현했다.

 

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

using namespace std;

int N, M;
vector<int> seq, ans;

void print_seq(int pos)
{
	if (ans.size() == M)
	{
		for(int i=0; i<ans.size(); ++i)
			cout << ans[i] <<' ';
		cout << '\n';
	}

	for (int i = pos; i < N; ++i)
	{
		ans.push_back(seq[i]);
		print_seq(i + 1);
		ans.pop_back();
	}
}

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

	seq.assign(N, 0);

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

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

	print_seq(0);
}