취미로 코딩하기

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

이번에 볼 문제는 백준 17500번 문제인 국경이다.
문제는 아래 링크를 확인하자.

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

입력으로 주어지는 \(N\)의 크기가 매우 작음(4 이하)을 확인하자. 실제로 \(N=4\)인 경우 좌상단 꼭짓점에서 우하단 꼭짓점으로 한 꼭짓점을 두 번 이상 경유하지 않고 이동하는 경로의 개수는 10000개도 되지 않는다.

따라서, 위와 같은 모든 경로를 백트래킹으로 전부 생성해보고, BFS 등으로 각 경로가 서로 다른 동물들이 다른 영역에 포함되게끔 섬을 나누는지 확인해 문제를 해결할 수 있다.

칸의 경계와 칸 자체를 모두 접근해야 하므로, 코드를 작성할 때 특별히 유의하여 이를 구현하자.

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

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

int N = 5;
int visited[5][5];
char board[11][11];
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
bool printed;
int vis[11][11];
set<char> st;
queue<pair<int, int>> que;
bool bfs(int sR, int sC) {
	st.clear();
	vis[sR][sC] = 1;
	que.push(make_pair(sR, sC));
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		if (board[r][c] != '.') st.insert(board[r][c]);
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (board[rr][cc]) continue;
			rr += dr[i], cc += dc[i];
			if (rr < 2 || rr >= N * 2 + 1 || cc < 2 || cc >= N * 2 + 1 || vis[rr][cc]) continue;
			vis[rr][cc] = 1;
			que.push(make_pair(rr, cc));
		}
	}
	return (st.size() <= 1);
}
void solve() {
	memset(vis, 0, sizeof(vis));
	for (int r = 2; r < N * 2 + 1; r += 2) {
		for (int c = 2; c < N * 2 + 1; c += 2) {
			if (vis[r][c]) continue;
			if (!bfs(r, c)) return;
		}
	}
	printed = 1;
	cout << "yes\n";
	for (int r = 0; r < N * 2 + 3; r++) {
		for (int c = 0; c < N * 2 + 3; c++) {
			if (c % 2 == 0 && c > 0 && c < N * 2 + 1) {
				if (board[r][c] == '-' || board[r][c] == '#') cout << board[r][c] << board[r][c] << board[r][c];
				else if (board[r][c]) cout << ' ' << board[r][c] << ' ' ;
				else cout << ' ' << ' ' << ' ';
			}
			else {
				if (board[r][c]) cout << board[r][c];
				else cout << ' ';
			}
		}
		cout << '\n';
	}
}

void func(int r, int c) {
	if (r == N && c == N) {
		if (!printed) solve();
	}
	visited[r][c] = 1;
	for (int i = 0; i < 4; i++) {
		int rr = r + dr[i], cc = c + dc[i];
		if (rr < 0 || rr > N || cc < 0 || cc > N || visited[rr][cc]) continue;
		if (i < 2) board[1 + r * 2][1 + c * 2 + dc[i]] = '-';
		else board[1 + r * 2 + dr[i]][1 + c * 2] = '|';
		func(rr, cc);
		if (i < 2) board[1 + r * 2][1 + c * 2 + dc[i]] = 0;
		else board[1 + r * 2 + dr[i]][1 + c * 2] = 0;
	}
	visited[r][c] = 0;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int c = 0; c < N * 2 + 3; c++) board[0][c] = board[N * 2 + 2][c] = '#';
	for (int r = 0; r < N * 2 + 3; r++) board[r][0] = board[r][N * 2 + 2] = '#';
	for (int r = 1; r < N * 2 + 3; r += 2) {
		for (int c = 1; c < N * 2 + 3; c += 2) {
			board[r][c] = '+';
		}
	}
	for (int r = 2; r < N * 2 + 1; r += 2) {
		for (int c = 2; c < N * 2 + 1; c += 2) {
			cin >> board[r][c];
		}
	}

	func(0, 0);
	if (!printed) cout << "no";
}

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

이번에 볼 문제는 백준 29779번 문제인 Colliding Encoding이다.
문제는 아래 링크를 확인하자.

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

주어지는 문자열들의 각 문자를 주어진 규칙대로 치환해 얻을 수 있는 변환된 문자열들 사이에 겹치는 것이 있는지 확인하는 문제이다. 주어진 작업을 그대로 구현해 문제를 해결하자.

한편, 문자열의 길이가 최대 9로 충분히 짧아 변환된 문자열을 정수로 기록하는 것으로 메모리를 절약해 실행 속도 향상을 노릴 수 있다. 다만, 이와 같은 풀이를 이용하고자 할 경우 0으로 시작하는 문자열과 leading zero가 있는 문자열은 구분이 되어야 하므로, 자릿수 없음을 나타내는 수를 별도로 하나 더 할당하는 방법, 자릿수를 같이 저장하는 방법 등의 예외처리가 추가로 필요하다.

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

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

int N;
set<ll> st;
int A[128];

void solve() {
	st.clear();
	for (char c = 'A'; c <= 'Z'; c++) cin >> A[c];
	cin >> N;
	for (int i = 0; i < N; i++) {
		string s; cin >> s;
		while (s.length() < 9) s += '#';
		ll val = 0;
		for (auto &l : s) val = val * 10 + A[l];
		st.insert(val);
	}
	if (st.size() < N) cout << "YES\n";
	else cout << "NO\n";
}

int T;

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

	A['#'] = 10;

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case #" << t << ": ";
		solve();
	}
}

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

이번에 볼 문제는 백준 19276번 문제인 Magic Trick이다.
문제는 아래 링크를 확인하자.

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

주어진 원순열을 하나의 사이클로 구성된 그래프로 생각하자. 이 때 각각의 주어지는 세 점의 묶음은 어떤 한 정점과 그와 인접한 두 정점들로 이루어져 있으므로, 각 묶음에서 두 정점을 고르면 그래프상에서의 두 점 사이의 거리가 1 또는 2가 됨을 알 수 있다.

추가로, \(n\)이 4보다 큰 경우 각 묶음으로부터 얻을 수 있는 두 정점 선택의 쌍을 모두 모으면 거리가 1인 쌍은 두 번씩 등장하며 2인 쌍은 한 번씩 등장하게 됨을 관찰할 수 있다. 이를 이용하면 주어진 원순열을 구성하는 에지가 무엇인지를 map 등을 이용해 판별할 수 있고, 이를 이용해 문제를 해결할 수 있다.

\(n=3\)인 경우는 가능한 원순열이 한 종류밖에 없으므로 자명한 답을 보인다. 또한 \(n=4\)인 경우 네 수 가운데 하나씩 빠진 묶음 4개가 항상 등장해야 하므로 입력이 유일하고, 이 경우 또한 자명한 답을 보인다. (한편, 아래의 코드는 이 경우들에 대해서도 제대로 된 답을 도출한다.)

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

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int N;
vector<int> G[200001];
map<pair<int, int>, int> mp;
bool visited[200001];

void dfs(int cur) {
	cout << cur << ' ';
	visited[cur] = 1;
	for (auto &nxt:G[cur]) {
		if (visited[nxt]) continue;
		dfs(nxt);
	}
}

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

	cin >> N;
	for (int k = 0; k < N; k++) {
		int x, y, z; cin >> x >> y >> z;
		mp[make_pair(min(x, y), max(x, y))]++;
		mp[make_pair(min(y, z), max(y, z))]++;
		mp[make_pair(min(z, x), max(z, x))]++;
	}

	for (auto &p:mp) {
		if (p.second > 1) G[p.first.first].emplace_back(p.first.second), G[p.first.second].emplace_back(p.first.first);
	}

	dfs(1);
}

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

이번에 볼 문제는 백준 1471번 문제인 사탕 돌리기이다.
문제는 아래 링크를 확인하자.

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

주어진 문제의 상황은 functional graph로 모델링되는데, 이러한 그래프는 어느 정점에서 출발하더라도 대응되는 사이클을 끝없이 돌게 된다.

따라서 주어진 그래프에서 사이클을 모두 찾고, 각 사이클로부터 사이클에 포함되지 않는 정점까지의 거리를 구하는 것으로 문제를 해결할 수 있다.

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

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

int N;
int G[200001];
vector<int> invG[200001];
int visited[200001];
int dist[200001];
queue<int> que;
int ans;

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int ii = i, val = 0;
		while (ii) {
			val += ii % 10;
			ii /= 10;
		}
		int nxt = i + val;
		if (nxt > N) nxt -= N;
		G[i] = nxt;
		invG[nxt].emplace_back(i);
	}
	for (int i = 1; i <= N; i++) {
		if (visited[i]) continue;
		int ii = i;
		while (!visited[ii]) {
			visited[ii] = i;
			ii = G[ii];
		}
		if (visited[ii] == i) {
			int iii = ii, cnt = 1;
			while (G[iii] != ii) {
				iii = G[iii], cnt++;
			}
			iii = ii;
			dist[iii] = cnt;
			que.push(iii);
			while (G[iii] != ii) {
				iii = G[iii];
				dist[iii] = cnt;
				que.push(iii);
			}
		}
	}
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		ans = max(ans, dist[cur]);
		for (auto &x:invG[cur]) {
			if (dist[x]) continue;
			dist[x] = dist[cur] + 1;
			que.push(x);
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 20913번 문제인 Mixtape Management이다.
문제는 아래 링크를 확인하자.

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

어떤 같은 자릿수의 서로 다른 두 양의 정수 \(A\)와 \(B\)에 대하여 \(A\)를 일정 횟수 연속으로 이어붙여 얻은 수와 \(B\)를 연속으로 이어붙여 얻은 수의 사전순 대소는 \(A\)와 \(B\)의 사전순 대소를 따라가며, 크기의 경우 이어붙인 횟수를 따라감을 확인하자.

따라서, 서로 다른 \(n\)개의 세자리 수를 준비한 뒤 수열의 \(i\)번째 수를 준비한 수 중 \(i\)번째 수를 반복한 수를 적으면 주어진 수들이 사전순으로 나열됨을 알 수 있다. 이제 각 수를 적절히 반복시켜 자릿수를 늘리는 것으로 문제 조건에 맞게 대소관계를 설정해 문제를 해결하자.

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

#include <iostream>
#include <string>
using namespace std;

int N;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		string s = to_string(i + 100);
		int x; cin >> x;
		while (x--) cout << s;
		cout << ' ';
	}
}

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

이번에 볼 문제는 백준 27503번 문제인 요가 수업이다.
문제는 아래 링크를 확인하자.

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

주어진 조건으로부터, 꼭 지켜져야 하는 규칙들은 다음과 같이 요약할 수 있다:

(1) \(M\)개의 동작 중, 대응되는 대체 동작이 있는 동작은 원래 동작과 대체 동작 중 적어도 하나의 동작을 해야 한다.

(2) \(M\)개의 동작 중, 대응되는 대체 동작이 없는 동작은 무조건 해야 한다.

(3) \(K\)가지 쌍에 해당하는 동작들은 두 동작 중 적어도 하나의 동작을 하지 않아야 한다.

위와 같은 위의 내용을 CNF로 치환하면 이 문제는 2-SAT문제로 변환된다. 따라서 주어진 문제를 implication graph로 변환 후 SCC를 구해 모순이 발생하는지 확인하는 것으로 문제를 선형시간에 해결할 수 있다.

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

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

int N, M, C, K;
bool chk[500001];
vector<int> G[1000001];
int dfidx, dfi[1000001];
int scidx, sci[1000001];
vector<int> stk;

int dfs(int cur) {
	stk.emplace_back(cur);
	int ret = dfi[cur] = ++dfidx;
	for (auto &nxt : G[cur]) {
		if (sci[nxt]) continue;
		if (dfi[nxt]) ret = min(ret, dfi[nxt]);
		else ret = min(ret, dfs(nxt));
	}
	if (ret == dfi[cur]) {
		scidx++;
		while (stk.back() != cur) {
			sci[stk.back()] = scidx;
			stk.pop_back();
		}
		sci[stk.back()] = scidx;
		stk.pop_back();
	}
	return ret;
}

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

	cin >> N >> M >> C >> K;
	while (M--) {
		int x; cin >> x;
		chk[x] = 1;
	}
	while (C--) {
		int x, y; cin >> x >> y;
		G[x + 500000].emplace_back(y);
		G[y + 500000].emplace_back(x);
		chk[x] = chk[y] = 0;
	}
	while (K--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y + 500000);
		G[y].emplace_back(x + 500000);
	}
	for (int i = 1; i <= N; i++) {
		if (chk[i]) G[i + 500000].emplace_back(i);
	}

	for (int i = 1; i <= N; i++) {
		if (!sci[i]) dfs(i);
		if (!sci[i + 500000]) dfs(i + 500000);
	}
	for (int i = 1; i <= N; i++) {
		if (sci[i] == sci[i + 500000]) {
			cout << "NO";
			return 0;
		}
	}

	cout << "YES";
}