취미로 코딩하기

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

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

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

dp[x][y]를 (1번 경찰차가 마지막으로 처리한 사건이 x, 2번 경찰차가 마지막으로 처리한 사건이 y)인 경우의 최소 이동거리라 하자. 이 때 dp값은 이 값은 x>y+1인 경우 dp[x-1][y] + (1번 경찰차가 x-1에서 x까지 이동한 거리), y>x+1인 경우 dp[x][y-1] + (2번 경찰차가 y-1에서 y까지 이동한 거리)로 계산할 수 있다. x=y+1인 경우에는 dp[i][y]의 최솟값(단, i는 y미만), y = x+1인 경우에는 dp[x][i]의 최솟값(단, i는 x 미만)이 된다. x와 y가 같은 경우는 존재할 수 없다.

위의 점화식을 이용해 문제를 해결하자. 어떤 경찰차를 실제로 움직였는지 역추적하는 과정은 위 계산을 진행하면서 각 과정의 최적해가 어떤 이전 단계로부터 왔는지를 별도의 배열에 저장하는 것으로 간단히 구현할 수 있다.

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

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

int N, W;
int dp[1001][1001]; // dp[x][y]: 1번 경찰차가 마지막으로 처리한 사건은 x, 2번 경찰차가 마지막으로 처리한 사건은 y
pair<int,int> backtrack[1001][1001];
bool visited[1001][1001];
int R1[1001], C1[1001], R2[1001], C2[1001];

int dist1(int i, int j) {
	return abs(R1[i] - R1[j]) + abs(C1[i] - C1[j]);
}

int dist2(int i, int j) {
	return abs(R2[i] - R2[j]) + abs(C2[i] - C2[j]);
}

int func(int x, int y) {
	int& ret = dp[x][y];
	if (visited[x][y]) return ret;
	visited[x][y] = 1;

	if (x > y + 1) ret = func(x - 1, y) + dist1(x - 1, x), backtrack[x][y] = make_pair(x - 1, y);
	else if (x + 1 < y) ret = func(x, y - 1) + dist2(y - 1, y), backtrack[x][y] = make_pair(x, y - 1);
	else {
		ret = 2000000007;
		if (x > y) {
			for (int i = 0; i < y; i++) {
				int val = func(i, y) + dist1(i, x);
				if (val < ret) ret = val, backtrack[x][y] = make_pair(i, y);
			}
		}
		else {
			for (int i = 0; i < x; i++) {
				int val = func(x, i) + dist2(i, y);
				if (val < ret) ret = val, backtrack[x][y] = make_pair(x, i);
			}
		}
	}

	return ret;
}

int ans = 2000000007, ansx, ansy;
vector<int> stk;

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

	cin >> N >> W;
	for (int i = 1; i <= W; i++) {
		cin >> R1[i] >> C1[i];
	}
	for (int i = 1; i <= W; i++) R2[i] = R1[i], C2[i] = C1[i];
	R1[0] = C1[0] = 1, R2[0] = C2[0] = N;
	
	dp[1][0] = dist1(0, 1), dp[0][1] = dist2(0, 1);
	visited[1][0] = visited[0][1] = 1;
	backtrack[1][0] = backtrack[0][1] = make_pair(0, 0);

	for (int i = 0; i < W; i++) {
		int val = func(i, W);
		if (val < ans) ans = val, ansx = i, ansy = W;
		val = func(W, i);
		if (val < ans) ans = val, ansx = W, ansy = i;
	}
	
	while (ansx + ansy) {
		if (ansx > ansy) stk.emplace_back(1);
		else stk.emplace_back(2);

		int nxtx = backtrack[ansx][ansy].first, nxty = backtrack[ansx][ansy].second;
		ansx = nxtx, ansy = nxty;
	}

	cout << ans << '\n';
	while (!stk.empty()) {
		cout << stk.back() << '\n';
		stk.pop_back();
	}
}

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

이번에 볼 문제는 백준 2617 문제인 구슬 찾기이다.
문제는 아래 링크를 확인하자.

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

주어진 구슬들 중, 자신보다 더 무거운게 확실한(주어진 조건들을 이용해 직접 추론 가능한) 구슬의 개수 또는 더 가벼운게 확실한 구슬의 개수가 N의 절반을 넘는 구슬의 개수를 세는 것으로 문제를 해결할 수 있다. 이러한 경우 해당 구슬의 무게가 전체의 중간이 될 수 없음은 자명하다. 그렇지 않은 경우 위상정렬 등을 이용하면 해당 구슬을 가운데 차례에 위치하게끔 하는 방법을 쉽게 얻을 수 있다. (구체적인 방법 서술은 생략한다.)

이를 구하기 위해, 주어진 무게관계들을 이용해 A가 B보다 더 무거움에 대응되는 방향에지로 만들어진 그래프와 A가 B보다 더 가벼움에 대응되는 방향에지로 만들어진 그래프를 만들자. 이 때, 각 그래프에서 어떤 노드 x로부터 다른 노드 y로 가는 경로가 존재한다는 것은 x와 y 사이의 무게 사이에 (그래프의 종류에 따른) 관계가 있음을 의미함을 관찰하자. 따라서 이와 같은 그래프를 이용하면 각 노드에서 이동할 수 있는 노드의 개수를 세는 것으로 문제를 해결할 수 있게 된다.

전체 구슬의 개수가 충분히 적으므로, 해당 값을 구하기 위해 각 노드를 출발점으로 하는 탐색을 일일이 시도하는 것으로도 문제를 충분히 해결할 수 있다.

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

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

int N, M;
vector<int> G1[100], G2[100];
int visited[100];

int func1(int x) {
	memset(visited, 0, sizeof(visited));
	int ret = 0;
	queue<int> que;
	que.push(x);
	visited[x] = 1;
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& nxt : G1[cur]) {
			if (visited[nxt]) continue;
			ret++, que.push(nxt);
			visited[nxt] = 1;
		}
	}

	return ret;
}

int func2(int x) {
	memset(visited, 0, sizeof(visited));
	int ret = 0;
	queue<int> que;
	que.push(x);
	visited[x] = 1;
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& nxt : G2[cur]) {
			if (visited[nxt]) continue;
			ret++, que.push(nxt);
			visited[nxt] = 1;
		}
	}

	return ret;
}

int ans;

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

	cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		G1[x].emplace_back(y);
		G2[y].emplace_back(x);
	}

	for (int i = 1; i <= N; i++) {
		if (func1(i) > N / 2 || func2(i) > N / 2) ans++;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 2619번 문제인 단순 사각형이다.
문제는 아래 링크를 확인하자.

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

주어진 잘린 영역이 단순 사각형이 아닐 필요충분조건 중 하나로 주어진 N개의 점 중 하나가 내각 270도의 꼭짓점으로 포함되어있어야 할 것이 있음을 관찰하자. 내각 270도의 꼭짓점이 존재하지 않는 다각형은 단순 사각형이 될 수밖에 없고, 그러한 각도를 가질 수 있는 꼭짓점은 문제 조건에 따라 주어진 N개의 점에서 나올 수밖에 없기 때문이다.

글쓴이는 구현을 편하게 하기 위해 먼저 주어진 그림을 각 점과 선의 "두께"를 1로 늘려 새로 그렸다. 그 다음, 이 새 그림에 존재하는 "단순 사각형이 아닌 영역"을 메워버린 다음(위의 필요충분조건 이용) (3) 남아있는 영역의 개수를 세는 것으로 문제를 해결하자. 단순 사각형이 아닌 영역을 모두 메우면 남는 영역은 각각 단순 사각형임을 확인하자.

시간제한에 맞춰 통과해야하므로, 먼저 주어진 좌표들을 압축하도록 하자.

한편, 주어지는 입력의 꼭짓점들이 다각형을 이루는 순서대로 주어진다는 보장이 지문에 없음에 유의하자. 따라서 주어진 꼭짓점들로부터 선분들을 찾는 것부터 시작하자. 다행히 문제의 조건을 만족하는 꼭짓점들이 주어지면 이러한 선분의 구성은 유일함을 알 수 있다.

이 모든 과정의 시간복잡도는 \(O(N^2)\)으로, 이는 문제를 해결하기에 충분한 값이다.

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

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

int N;
pair<int, int> points[1000];
vector<int> R, C;
int compr_R[10001], compr_C[10001];
char board[1001][1001];

bool comp(pair<int, int>& p1, pair<int, int>& p2) {
	if (p1.second != p2.second) return p1.second < p2.second;
	return p1.first < p2.first;
}

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

void dfs(int r, int c) {
	board[r][c] = 2;
	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 || board[rr][cc]) continue;
		dfs(rr, cc);
	}
}

int cnt;

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

	cin >> N;

	for (int i = 0; i < N; i++) {
		int r, c; cin >> r >> c;
		points[i] = make_pair(r, c);
		R.emplace_back(r), C.emplace_back(c);
	}

	sort(R.begin(), R.end());
	for (int i = 0, ridx = 0; i < N; i++) {
		if (!compr_R[R[i]]) compr_R[R[i]] = ridx++ * 2 + 1;
	}

	sort(C.begin(), C.end());
	for (int i = 0, cidx = 0; i < N; i++) {
		if (!compr_C[C[i]]) compr_C[C[i]] = cidx++ * 2 + 1;
	}
	
	for (int i = 0; i < N; i++) {
		points[i].first = compr_R[points[i].first], points[i].second = compr_C[points[i].second];
	}
	
	sort(points, points + N);
	for (int i = 0; i < N; i += 2) {
		int r = points[i].first, c1 = points[i].second, c2 = points[i + 1].second;
		if (c1 > c2) swap(c1, c2);
		for (int c = c1; c <= c2; c++) {
			board[r][c] = 1;
		}
	}

	sort(points, points + N, comp);
	for (int i = 0; i < N; i += 2) {
		int r1 = points[i].first, r2 = points[i + 1].first, c = points[i].second;
		if (r1 > r2) swap(r1, r2);
		for (int r = r1; r <= r2; r++) {
			board[r][c] = 1;
		}
	}

	for (int i = 0; i < N; i++) {
		int r = points[i].first, c = points[i].second;
		if (board[r + 1][c] == 1 && board[r][c + 1] == 1) {
			if (!board[r - 1][c - 1]) dfs(r - 1, c - 1);
		}
		else if (board[r + 1][c] == 1 && board[r][c - 1] == 1) {
			if (!board[r - 1][c + 1]) dfs(r - 1, c + 1);
		}
		else if (board[r - 1][c] == 1 && board[r][c + 1] == 1) {
			if (!board[r + 1][c - 1]) dfs(r + 1, c - 1);
		}
		else if (board[r - 1][c] == 1 && board[r][c - 1] == 1) {
			if (!board[r + 1][c + 1]) dfs(r + 1, c + 1);
		}
	}

	for (int r = 0; r <= N; r++) {
		for (int c = 0; c <= N; c++) {
			if (!board[r][c]) dfs(r, c), cnt++;
		}
	}

	cout << cnt;
}