본문 바로가기
code/BOJ

백준 구슬탈출 1~4

장동욱 2019. 10. 12. 23:14

 

문제:
구슬 탈출: 백준 13459

구슬 탈출 2: 백준 13460

구슬 탈출 3: 백준 15644
구슬 탈출 4: 백준 15653

 

코드:

1. 구슬탈출:

#include <iostream>
#include <queue>
#define f(i, n) for(int i = 0; i < (n); ++i)
#define v(R, B) vst[(R).first][(R).second][(B).first][(B).second]
using namespace std;
typedef pair<int, int> p;
int N, M;
char map[10][10];
bool vst[10][10][10][10];
int dn[] = { -1, 0, 1, 0 };
int dm[] = { 0, 1, 0, -1 };
bool frst(p &R, p &B, int d) {
	switch (d) {
	case 0: return R.first < B.first;
	case 1: return R.second > B.second;
	case 2: return R.first > B.first;
	case 3: return R.second < B.second;
	}
}
p move(p A, p &B, int d) {
	while (1) {
		A.first += dn[d], A.second += dm[d];
		if (map[A.first][A.second] == 'O')
			return A;	/* 2 */
		if (map[A.first][A.second] == '#' || A == B) {
			A.first -= dn[d], A.second -= dm[d];
			return A;
		}
	}
}
struct qnode {
	p R, B;
};
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	p R, B;
	f(n, N) f(m, M) {
		cin >> map[n][m];
		switch (map[n][m]) {
		case 'R': R = make_pair(n, m); break;
		case 'B': B = make_pair(n, m); break;
		}
	}
	bool ans;
	v(R, B) = 1;
	queue<qnode> q;
	q.push({ R, B });
	int t = 0;
	while (!q.empty()) {
		int qs = q.size();
		while (qs--) {
			qnode pt = q.front(); q.pop();
			int Rn = pt.R.first, Rm = pt.R.second;
			int Bn = pt.B.first, Bm = pt.B.second;
			bool Rout = map[Rn][Rm] == 'O';
			bool Bout = map[Bn][Bm] == 'O';
			if (Bout) continue;
			if (Rout) {
				ans = 1;
				goto out;
			}
			f(d, 4) {
				p nR, nB;
				if (frst(pt.R, pt.B, d))	{ nR = move(pt.R, pt.B, d); nB = move(pt.B, nR, d); }
				else				{ nB = move(pt.B, pt.R, d); nR = move(pt.R, nB, d); }
				if (v(nR, nB)) continue;
				v(nR, nB) = 1;
				q.push({ nR, nB });
			}
		}
		if (t == 10)
			break;
		++t;
	}
	ans = 0;
out:
	cout << ans;
	return 0;
}

2. 구슬 탈출 2:

#include <iostream>
#include <queue>
#define f(i, n) for(int i = 0; i < (n); ++i)
#define v(R, B) vst[(R).first][(R).second][(B).first][(B).second]
using namespace std;
typedef pair<int, int> p;
int N, M;
char map[10][10];
bool vst[10][10][10][10];
int dn[] = { -1, 0, 1, 0 };
int dm[] = { 0, 1, 0, -1 };
bool frst(p &R, p &B, int d) {
	switch (d) {
	case 0: return R.first < B.first;
	case 1: return R.second > B.second;
	case 2: return R.first > B.first;
	case 3: return R.second < B.second;
	}
}
p move(p A, p &B, int d) {
	while (1) {
		A.first += dn[d], A.second += dm[d];
		if (map[A.first][A.second] == 'O')
			return A;	/* 2 */
		if (map[A.first][A.second] == '#' || A == B) {
			A.first -= dn[d], A.second -= dm[d];
			return A;
		}
	}
}
struct qnode {
	p R, B;
};
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	p R, B;
	f(n, N) f(m, M) {
		cin >> map[n][m];
		switch (map[n][m]) {
		case 'R': R = make_pair(n, m); break;
		case 'B': B = make_pair(n, m); break;
		}
	}
	v(R, B) = 1;
	queue<qnode> q;
	q.push({ R, B });
	int t = 0;
	while (!q.empty()) {
		int qs = q.size();
		while (qs--) {
			qnode pt = q.front(); q.pop();
			int Rn = pt.R.first, Rm = pt.R.second;
			int Bn = pt.B.first, Bm = pt.B.second;
			bool Rout = map[Rn][Rm] == 'O';
			bool Bout = map[Bn][Bm] == 'O';
			if (Bout) continue;
			if (Rout) goto out;
			f(d, 4) {
				p nR, nB;
				if (frst(pt.R, pt.B, d))	{ nR = move(pt.R, pt.B, d); nB = move(pt.B, nR, d); }
				else				{ nB = move(pt.B, pt.R, d); nR = move(pt.R, nB, d); }
				if (v(nR, nB)) continue;
				v(nR, nB) = 1;
				q.push({ nR, nB });
			}
		}
		if (t == 10)
			break;
		++t;
	}
	t = -1;
out:
	cout << t;
	return 0;
}

3. 구슬 탈출 3:

경로를 출력하기 위해 방문을 나타내는 배열 vst의 데이터형을 bool에서 부모노드의 R, B좌표와 방향을 필드로 하는 구조체로 변경하고자 했다. 탐색이 성공적인 경우, 마지막 상태에서 시작해 vst를 따라 초기상태의 R, B에 이르기 까지 거쳐온 방향을 알 수 있다. 하지만 이 방법은 런타임에러와 메모리 초과가 발생해서 부모를 표시하는 방식을 변경했다.

탐색 조건에 위반하지 않는 노드에 번호 v를 부여하고, 자식 노드 번호의 prnt값에 자식 노드의 이동 방향과, 부모의 노드 번호를 저장했다. 탐색이 성공적인 경우, prnt 배열을 따라가면서 경로 상의 모든 이동 방향을 역으로 얻을 수 있고, 이를 벡터에 넣어 다시 역순으로 출력해 문제에서 요구하는 순서대로 출력할 수 있다.

#include <iostream>
#include <queue>
#include <vector>
#define f(i, n) for(int i = 0; i < (n); ++i)
#define v(R, B) vst[(R).first][(R).second][(B).first][(B).second]
using namespace std;
typedef pair<int, int> p;
int N, M;
char map[10][10];
bool vst[10][10][10][10];
pair<int, int> prnt[10000]; int v = 1, ve;
int dn[] = { -1, 0, 1, 0 };
int dm[] = { 0, 1, 0, -1 };
char dr[] = { 'U', 'R', 'D', 'L' };
bool frst(p &R, p &B, int d) {
	switch (d) {
	case 0: return R.first < B.first;
	case 1: return R.second > B.second;
	case 2: return R.first > B.first;
	case 3: return R.second < B.second;
	}
}
p move(p A, p &B, int d) {
	while (1) {
		A.first += dn[d], A.second += dm[d];
		if (map[A.first][A.second] == 'O')
			return A;	/* 2 */
		if (map[A.first][A.second] == '#' || A == B) {
			A.first -= dn[d], A.second -= dm[d];
			return A;
		}
	}
}
struct qnode {
	p R, B;
	int v;
};
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	p R, B;
	f(n, N) f(m, M) {
		cin >> map[n][m];
		switch (map[n][m]) {
		case 'R': R = make_pair(n, m); break;
		case 'B': B = make_pair(n, m); break;
		}
	}
	v(R, B) = 1;
	prnt[v] = make_pair(-1, -1);
	queue<qnode> q;
	q.push({ R, B, v });
	int t = 0;
	while (!q.empty()) {
		int qs = q.size();
		while (qs--) {
			qnode pt = q.front(); q.pop();
			int Rn = pt.R.first, Rm = pt.R.second;
			int Bn = pt.B.first, Bm = pt.B.second;
			bool Rout = map[Rn][Rm] == 'O';
			bool Bout = map[Bn][Bm] == 'O';
			if (Bout) continue;
			if (Rout) {
				ve = pt.v;
				goto out;
			}
			f(d, 4) {
				p nR, nB;
				if (frst(pt.R, pt.B, d))	{ nR = move(pt.R, pt.B, d); nB = move(pt.B, nR, d); }
				else				{ nB = move(pt.B, pt.R, d); nR = move(pt.R, nB, d); }
				if (v(nR, nB)) continue;
				prnt[++v] = { pt.v, d };
				v(nR, nB) = 1;
				q.push({ nR, nB, v });
			}
		}
		if (t == 10)
			break;
		++t;
	}
	cout << -1;
	return 0;
out:
	cout << t << '\n';
	vector<int> buf;
	for (int v = ve; prnt[v].first != -1; v = prnt[v].first)
		buf.push_back(prnt[v].second);
	for (; buf.size(); buf.pop_back())
		cout << dr[buf.back()];
	return 0;
}

4. 구슬 탈출 4:

앞의 문제들과 달리 구슬 이동에 횟수 제한이 없고, 탐색을 성공시킬 수 없다면 -1을 출력해야 한다. vst에 의해 제한되는 R, B 좌표 조합의 개수는 10^4개다. 한 번 이동할 때(BFS level 하나)에 vst가 한 번만 갱신된다고 가정하면 depth 10000 전에는 탐색이 완료되어야 하므로 탐색 가능 기준을 t == 10000으로 잡는다.

#include <iostream>
#include <queue>
#define f(i, n) for(int i = 0; i < (n); ++i)
#define v(R, B) vst[(R).first][(R).second][(B).first][(B).second]
using namespace std;
typedef pair<int, int> p;
int N, M;
char map[10][10];
bool vst[10][10][10][10];
int dn[] = { -1, 0, 1, 0 };
int dm[] = { 0, 1, 0, -1 };
bool frst(p &R, p &B, int d) {
	switch (d) {
	case 0: return R.first < B.first;
	case 1: return R.second > B.second;
	case 2: return R.first > B.first;
	case 3: return R.second < B.second;
	}
}
p move(p A, p &B, int d) {
	while (1) {
		A.first += dn[d], A.second += dm[d];
		if (map[A.first][A.second] == 'O')
			return A;	/* 2 */
		if (map[A.first][A.second] == '#' || A == B) {
			A.first -= dn[d], A.second -= dm[d];
			return A;
		}
	}
}
struct qnode {
	p R, B;
};
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	p R, B;
	f(n, N) f(m, M) {
		cin >> map[n][m];
		switch (map[n][m]) {
		case 'R': R = make_pair(n, m); break;
		case 'B': B = make_pair(n, m); break;
		}
	}
	v(R, B) = 1;
	queue<qnode> q;
	q.push({ R, B });
	int t = 0;
	while (!q.empty()) {
		int qs = q.size();
		while (qs--) {
			qnode pt = q.front(); q.pop();
			int Rn = pt.R.first, Rm = pt.R.second;
			int Bn = pt.B.first, Bm = pt.B.second;
			bool Rout = map[Rn][Rm] == 'O';
			bool Bout = map[Bn][Bm] == 'O';
			if (Bout) continue;
			if (Rout) goto out;
			f(d, 4) {
				p nR, nB;
				if (frst(pt.R, pt.B, d))	{ nR = move(pt.R, pt.B, d); nB = move(pt.B, nR, d); }
				else				{ nB = move(pt.B, pt.R, d); nR = move(pt.R, nB, d); }
				if (v(nR, nB)) continue;
				v(nR, nB) = 1;
				q.push({ nR, nB });
			}
		}
		if (t == 1000)
			break;
		++t;
	}
	t = -1;
out:
	cout << t;
	return 0;
}
저작자표시 비영리 변경금지

'code/BOJ' Related Articles

티스토리툴바