취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2583번 문제인 영역 구하기이다.
문제는 아래 링크를 확인하자.

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

주어지는 영역의 크기가 크지 않으므로, 직접 직사각형에 포함되는 칸을 반복문으로 칠한 뒤 connected component의 개수를 세어주자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int R, C;
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
bool board[100][100];

int bfs(int r, int c) {
	int ret = 0;
	queue<pair<int, int>> que;
	que.push({ r,c });
	while (!que.empty()) {
		ret++;
		r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (board[rr][cc]) continue;
			board[rr][cc] = 1;
			que.push({ rr,cc });
		}
	}

	return ret;
}

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

	int K; cin >> R >> C >> K;
	while (K--) {
		int r1, c1, r2, c2; cin >> c1 >> r1 >> c2 >> r2;
		for (int r = r1; r < r2; r++) {
			for (int c = c1; c < c2; c++) {
				board[r][c] = 1;
			}
		}
	}

	vector<int> ans;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c]) continue;
			board[r][c] = 1;
			ans.emplace_back(bfs(r, c));
		}
	}

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

	cout << ans.size() << '\n';
	for (auto a : ans) cout << a << ' ';
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 8112번 문제인 0과 1 - 2이다.
문제는 아래 링크를 확인하자.

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

8111번 문제에서 T가 커지고 N이 작아진 문제이다.

8111번 풀이글에서의 풀이를 그대로 쓰면 긴 문자열을 계속 복사하는 데에는 문자열의 길이만큼의 시간복잡도가 필요하여 시간초과가 나므로 그 대신 백트래킹을 통해 답안을 구해주자.

각 "나머지" 별로, 그 나머지를 갖게 하는 최소의 숫자는 BFS의 탐색순서로 만들어진 BFS 트리를 따라 거꾸로 가는 것이므로 이를 이용해 백트래킹이 가능하다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

int ans[1000001];
int visited[1000001];
int parent[1000001];

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

	int N; cin >> N;
	while (N--) {
		memset(visited, 0, sizeof(visited));
		int x; cin >> x;
		if (x == 1) cout << 1 << '\n';
		else {
			queue<int> que;
			ans[1] = 1;
			que.push(1);
			while (!que.empty()) {
				int r = que.front(); que.pop();
				if (r == 0) {
					vector<int> vec;
					int temp = 0;
					while (temp != 1) {
						vec.emplace_back(ans[temp]);
						temp = parent[temp];
					}
					vec.emplace_back(1);
					if (vec.size() <= 100) {
						for (auto iter = vec.rbegin(); iter != vec.rend(); iter++) cout << *iter;
						cout << '\n';
					}
					else cout << "BRAK\n";
					break;
				}
				int rr = r * 10 % x;
				if (!visited[rr]) {
					visited[rr] = 1;
					ans[rr] = 0;
					parent[rr] = r;
					que.push(rr);
				}
				rr = (r * 10 + 1) % x;
				if (!visited[rr]) {
					visited[rr] = 1;
					ans[rr] = 1;
					parent[rr] = r;
					que.push(rr);
				}
			}
			if (!visited[0]) cout << "BRAK\n";
		}
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 8111번 문제인 0과 1이다.
문제는 아래 링크를 확인하자.

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

이 문제에서는 0과 1로만 이루어진 100자리 이하의 자연수 중 N의 배수를 찾는 문제이다.

100자리의 자연수를 들고 있기는 어려우므로, N의 나머지만을 보관하며 BFS를 해주자.

BFS를 하면 작은 자릿수의 숫자부터 탐색을 하게 되고, 이미 방문했던 "나머지"를 갖는 숫자가 나온다면 이 수는 이미 이전 단계에서 나온 같거나 작은 자릿수의 먼저 방문한 수와 이후로 똑같은 나머지들을 갖는 수들을 탐색해나가게 되므로 pruning(가지치기)을 해주자.

이와 같이 탐색하면 N별로 나올 수 있는 서로 다른 나머지 N개만을 탐색하고 탐색을 종료하게 되므로 실제로 방문하는 수의 경우의 수가 적어지므로 이 문제를 충분히 해결할 수 있다.

단, N의 범위가 100만까지 가능한 #8112번 문제는 아래 코드와 같이 제출하면 시간초과가 난다. 그 이유는 문자열을 계속 복사하여 집어넣는 데에 시간이 많이 소요되기 때문이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
using namespace std;

int visited[20001];

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

	int N; cin >> N;
	while (N--) {
		memset(visited, 0, sizeof(visited));
		int x; cin >> x;
		if (x == 1) cout << 1 << '\n';
		else {
			queue<pair<string, int>> que;
			que.push({ "1",1 });
			while (!que.empty()) {
				string s = que.front().first; int r = que.front().second; que.pop();
				if (r == 0) {
					if (s.length() <= 100) cout << s << '\n';
					else cout << "BRAK\n";
				}
				if (!visited[(r * 10) % x]) {
					visited[(r * 10) % x] = 1;
					que.push({ s + "0", (r * 10) % x });
				}
				if (!visited[(r * 10 + 1) % x]) {
					visited[(r * 10 + 1) % x] = 1;
					que.push({ s + "1", (r * 10 + 1) % x });
				}
			}
			if (!visited[0]) cout << "BRAK\n";
		}
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2800번 문제인 괄호 제거이다.
문제는 아래 링크를 확인하자.

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

이 문제는 주어진 수식 문자열에서 짝이 맞는 괄호들을 일부 제거한 문자열들을 사전순으로 출력하는 문제이다.

문자열을 둘러보며 짝이 맞는 괄호쌍의 위치를 스택을 이용하여 구해주고, 이 쌍들을 각각 포함하는 경우와 포함하지 않는 경우를 전부 탐색하여 한 벡터에 담은 뒤 정렬하는 것으로 문제를 해결할 수 있다.

식 하나를 여러 쌍의 괄호가 감쌀 경우 위와 같이 처리한 경우 중복되는 수식이 나온다는 점을 유의하여 구현하자. 예를 들면 ((((1+2))))와 같은 수식의 처리에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;

int arr[201];
int P, slen;
vector<pair<int, int>> p_pair;
string s;
vector<string> ans;

void func(int N) {
	if (N == P) {
		string ret = "";
		for (int i = 0; i < slen; i++) {
			if (arr[i]) continue;
			ret += s[i];
		}
		ans.emplace_back(ret);
	}
	else {
		int x = p_pair[N].first, y = p_pair[N].second;
		arr[x] = arr[y] = 1;
		func(N + 1);
		arr[x] = arr[y] = 0;
		func(N + 1);
	}
}

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

	stack<int> stk;
	cin >> s;
	slen = s.length();
	for (int i = 0; i < slen; i++) {
		if (s[i] == '(') stk.push(i);
		else if (s[i] == ')') {
			p_pair.push_back({ stk.top(),i });
			stk.pop();
		}
	}

	P = p_pair.size();
	
	func(0);

	sort(ans.begin(), ans.end());
	
	int len = ans.size();
	for (int i = 1; i < len; i++) {
		if (ans[i] == ans[i - 1]) continue;
		cout << ans[i] << '\n';
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1595번 문제인 북쪽나라의 도로이다.
문제는 아래 링크를 확인하자.

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

트리의 지름을 구하는 문제이다. 이 문제에서는 dp를 이용하여 트리의 지름을 구해보았다.

트리의 한 노드(1번)을 루트로 잡고, 다음과 같은 규칙을 생각하여 dp를 하자:

"현재 노드를 루트로 하는 서브트리에서, 이 루트를 지나는 최장경로의 길이는 가장 긴 두개의 자식방향의 경로 2개의 길이의 합과 같다"

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

vector<pair<int, ll>> G[10001];
bool visited[10001];

ll ans = 0;
ll dfs(int current, int parent) {
	ll ret1 = 0, ret2 = 0;
	for (auto np : G[current]) {
		int node = np.first; ll d = np.second;
		if (node == parent) continue;
		d += dfs(node, current);
		if (d > ret1) {
			ret2 = ret1; ret1 = d;
		}
		else if (d > ret2) ret2 = d;
	}
	ans = max(ans, ret1 + ret2);
	return ret1;
}

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

	int x, y; ll d;
	while (cin >> x >> y >> d) {
		G[x].push_back({ y,d });
		G[y].push_back({ x,d });
	}

	dfs(1, 0);

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5913번 문제인 준규와 사과이다.
문제는 아래 링크를 확인하자.

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

5행 5열의 농장에서 좌상단 칸으로부터 우하단 칸까지 모든 사과나무를 한번씩 방문하면서 가는 경로의 수를 구하는 문제이다.

농장의 크기가 작고, 농장을 그래프로 나타냈을 때 에지의 개수가 많지 않으므로(많아야 한 사과나무 주변에 있는 사과나무는 상하좌우 넷 뿐임을 생각하자) 그래프 위에서의 완전탐색을 통해 문제를 해결할 수 있다.

도착점에 도착했을 때 모든 사과나무를 들리고 왔는지 확인하기 위하여 방문한 칸 수를 변수로 이용하였다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N = 5, total;
bool visited[22][22];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

int cnt = 0;
void dfs(int curr, int curc, int visitcnt) {
	if (curr == N - 1 && curc == N - 1) {
		if (visitcnt == total) cnt++;
	}
	else {
		for (int i = 0; i < 4; i++) {
			int rr = curr + dr[i], cc = curc + dc[i];
			if (rr < 0 || rr >= N || cc < 0 || cc >= N) continue;
			if (visited[rr][cc]) continue;
			visited[rr][cc] = 1;
			dfs(rr, cc, visitcnt + 1);
			visited[rr][cc] = 0;
		}
	}
}

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

	int K;  cin >> K;
	total = 25 - K;

	while (K--) {
		int x, y; cin >> x >> y; x--; y--;
		visited[x][y] = 1;
	}

	visited[0][0] = 1;
	dfs(0, 0, 1);

	cout << cnt;
}