아인스트라세의 SW 블로그

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

배열 돌리기 시리즈 첫번째 문제입니다.

N, M이 최대 300으로 값이 그리 크지 않으므로, 정말 하나하나 다 돌려보면 답이 나옵니다.

가장 바깥부터 해서 R만큼 돌린 위치에 값을 저장하는 식으로 코드를 작성해 보았습니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int A[303][303];
int B[303][303];
const int mx[] = { +1, +0, -1, +0 };
const int my[] = { +0, +1, +0, -1 };
int main() {
	int N, M, R;
	scanf("%d%d%d", &N, &M, &R);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &A[i][j]);
		}
	}
	pii p[4];
	int sero = N - 1;
	int garo = M - 1;
	int round = 2 * (sero + garo);
	int stage = 0;

	p[0].first = p[0].second = stage;

	p[1].first = sero;
	p[1].second = stage;

	p[2].first = sero;
	p[2].second = garo;
	
	p[3].first = stage;
	p[3].second = garo;

	while (garo > 0 && sero > 0) {
		// Process (Write to B)
		int rotate = R % round;
		int sx, sy, dx, dy;
		sx = dx = p[0].first;
		sy = dy = p[0].second;
		int d1, d2;
		d1 = d2 = 0;
		for (int i = 0; i < rotate; i++) {
			dx += mx[d2];
			dy += my[d2];
			if (dx == p[(d2 + 1) % 4].first && dy == p[(d2 + 1) % 4].second) {
				d2 = (d2 + 1) % 4;
			}
		}
		for (int i = 0; i < round; i++) {
			B[dx][dy] = A[sx][sy];
			sx += mx[d1];
			sy += my[d1];
			if (sx == p[(d1 + 1) % 4].first && sy == p[(d1 + 1) % 4].second) {
				d1 = (d1 + 1) % 4;
			}
			dx += mx[d2];
			dy += my[d2];
			if (dx == p[(d2 + 1) % 4].first && dy == p[(d2 + 1) % 4].second) {
				d2 = (d2 + 1) % 4;
			}
		}

		// Process End
		sero -= 2;
		garo -= 2;
		round -= 8;
		stage += 1;
		p[0].first = p[0].second = stage;

		p[1].first = stage + sero;
		p[1].second = stage;

		p[2].first = stage + sero;
		p[2].second = stage + garo;

		p[3].first = stage;
		p[3].second = stage + garo;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			printf("%d", B[i][j]);
			if (j + 1 < M) putchar(' ');
		}
		putchar('\n');
	}
}

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

백준저지 17472번 문제 다리 만들기 2문제입니다.

N, M이 10으로 크지 않고 섬의 개수도 6개 밖에 안되므로, 하나하나씩 직접 찾아가도 크게 문제가 없습니다.

대충 단계는 다음과 같습니다.

1. Flood Fill로 모든 섬 찾기

2. 다리를 놓을 수 있는 모든 경우를 체크 함

3. 섬을 Graph의 Vertex로, 다리를 놓는 경우를 Edge로 모델링함

4. 그래프에 대한 최소 스패닝 트리(MST: Minimum Spanning Tree)를 구한다.

5. MST의 길이를 리턴, MST를 구할 수 없는 경우 -1를 리턴.

1번은 재귀를 이용한 dfs로 간단하게 짯으며(find_island 함수), 하는 과정에 물과 맞닿아 있는 좌표는 별도로 표기를 했습니다.

2번은 try_bridge 함수에서 체크를 했고, 한쪽 방향으로 계속 전진하며 다른 섬을 만나거나 맵 밖으로 나갈때까지 전진한 뒤 다리의 조건이 되는지를 체크했습니다.

4번은 MST를 크루스칼 알고리즘을 이용해서 구했습니다. Edge를 가장 짧은 길이순으로 소팅한 뒤, 하나씩 포함할 것인지 아닌지를 DSU(Disjoint Set 혹은 Union Find 자료구조)로 체크하면서 합쳤습니다.

코드입니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int N, M;
int field[11][11];

#define NOT_FOUND -1
#define WATER 0
//섬은 1~6의 숫자 값을 갖는다.
struct Pos {
	int x, y;
};
struct Bridge {
	int src, dest, len;
	bool operator<(const struct Bridge& rhs) const {
		return len < rhs.len;
	}
};
bool isin(Pos p) {
	return p.x >= 0 && p.y >= 0 && p.x < N && p.y < M;
}
struct Island {
	vector<Pos> edge; //물과 맞닿아있는 지점 좌표(다리 지을 수 있는지 체크용)
};
vector<Bridge> bridges;
Island islands[7];
const Pos d[4] = { {0, +1}, {+1, 0}, {-1, 0}, {0, -1} };
void find_island(Pos pos, int id) {
	field[pos.x][pos.y] = id;
	int water = 0;
	for (int k = 0; k < 4; k++) {
		Pos nx = { pos.x + d[k].x, pos.y + d[k].y };
		if (isin(nx)) {
			if (field[nx.x][nx.y] == NOT_FOUND) {
				find_island(nx, id);
			}
			else if (field[nx.x][nx.y] == WATER) {
				water++;
			}
		}
	}
	if (water) {
		islands[id].edge.push_back(pos);
	}
}
void try_bridge(const Pos pos) {
	const int id = field[pos.x][pos.y];
	for (int k = 0; k < 4; k++) {
		Pos p = { pos.x + d[k].x, pos.y + d[k].y };
		int len = 0;
		int dest = 0;
		while (isin(p) && field[p.x][p.y] == 0) {
			p.x += d[k].x;
			p.y += d[k].y;
			len++;
		}
		if (isin(p)) {
			dest = field[p.x][p.y];
		}
		if (len >= 2 && dest) {
			bridges.push_back({ id, dest, len });
		}
	}
}
int dsu[7];
int dsu_find(int p) {
	while (dsu[p] != p) {
		p = dsu[p];
	}
	return p;
}
int main() {
	int island_cnt = 1;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> field[i][j];
			if (field[i][j]) field[i][j] = -1;
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (field[i][j] == NOT_FOUND) {
				dsu[island_cnt] = island_cnt;
				find_island({ i, j }, island_cnt++);
			}
		}
	}
	for (int i = 1; i < island_cnt; i++) {
		for (Pos p : islands[i].edge) {
			try_bridge(p);
		}
	}

	// 최소 스패닝 트리 만들기
	sort(bridges.begin(), bridges.end());
	int total_len = 0;
	for (auto b : bridges) {

		if (dsu_find(b.src) != dsu_find(b.dest)) {
			total_len += b.len;
			// Disjoint Set Merge
			dsu[dsu_find(b.src)] = dsu_find(b.dest);
		}
	}

	// 최소 스패닝 트리에 모든 섬이 포함되었는지 확인
	int dsu_first = dsu_find(1);
	for (int i = 2; i < island_cnt; i++) {
		if (dsu_first != dsu_find(i)) {
			total_len = -1;
		}
	}
	cout << total_len << endl;
	return 0;
}

webhacking.kr 홈페이지가 새단장을 했습니다.

사이트 운영자가 oldzomebie님에서 rubiya님으로 바뀌게 되었고, 기존에 고장난 문제들도 고치고, 너무 구식인 문제들도 새로 업데이트하고 등등 여러모로 고생하셔서 새로이 오픈하였다고 합니다.

아직 100% 완전히 다 업데이트가 된 것은 아니지만, 문제를 풀 수 있게 되었습니다.

그 기념으로 1번 문제 풀이를 해보도록 하겠습니다.

view-source를 누르면 위와 같이 소스를 확인할 수 있습니다.

쿠키값이 5보다 크되, 6이상인 값이 되어서는 안됩니다.

크롬에서 F12를 눌러서 개발자 도구를 킨 뒤, 쿠키값을 확인해보겠습니다.

지금은 쿠키값이 1로 되어있는데, 5.5로 값을 변경해보도록 하겠습니다.

그리고 view-source가 아닌 페이지로 이동을 하면

문제가 풀렸다고 나옵니다.