[백준 13459] 구슬 탈출 (C++)

문제 링크: https://www.acmicpc.net/problem/13459

13459번: 구슬 탈출

 

 

1. 주의할 점

- 최대 10번만 기울일 수 있다. 10번 이전에 구멍을 도착한다면 더 이상 확인할 필요가 없다.

- DFS 과정마다 확인할 경우, 이전 정보를 기억해야한다.

 

2. 구현

- DFS를 10번 모두 돌린 이후, 확인하는 방법이 있다(최소 4^10만큼의 시간이 소요된다)

- DFS를 한번 할 때 마다, 확인하는 방법이 있다(위의 방법보다 시간이 훨씬 줄어든다)

- 2가지 방법 모두 빨간구슬과 파란구슬의 위치를 기억하고, 기울인다.

  파란구슬이 구멍에 빠질 수 있는 경우 -> 해당 경우 제외

  빨간구슬만 빠지는 경우 -> 1 출력(이후 과정은 확인 필요없음)

  2개의 구슬이 겹쳐지는 경우, 기울인 방향과 기울이기 전 방향을 고려하여 조정한다

 

[DFS 10번 이후 확인]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int row, col;
bool finish = false;
struct info {
	int x, y;
};
info tmp;
vector<info> v[2];
vector<int> order;
char arr[10][10];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

void move() {
	int rcx = v[0][0].x; int rcy = v[0][0].y;
	int bcx = v[1][0].x; int bcy = v[1][0].y;
	for (int i = 0; i < 10; i++) {
		int cd = order[i];
		int nrx = rcx; int nry = rcy; int nbx = bcx; int nby = bcy;
		bool fin_red = false, fin_blue = false;
		while (1) {
			nrx += dx[cd];
			nry += dy[cd];
			if (nrx >= 0 && nry >= 0 && nrx < col && nry < row && arr[nry][nrx] != '#') {
				if (arr[nry][nrx] == 'O') {
					fin_red = true;
					break;
				}
			}
			else {
				nrx -= dx[cd];
				nry -= dy[cd];
				break;
			}
		}
		while (1) {
			nbx += dx[cd];
			nby += dy[cd];
			if (nbx >= 0 && nby >= 0 && nbx < col && nby < row && arr[nby][nbx] != '#') {
				if (arr[nby][nbx] == 'O') {
					fin_blue = true;
					break;
				}
			}
			else {
				nbx -= dx[cd];
				nby -= dy[cd];
				break;
			}
		}
		if (fin_blue) 	break;	//파란공이 나가는 경우
		if (fin_red) {			//빨간공만 나가는 경우
			finish = true;
			break;
		}
		if (nrx == nbx && nry == nby) {
			if (cd == 0) {
				if (rcy < bcy) nby += 1;
				else nry += 1;
			}
			else if (cd == 1) {
				if (rcx < bcx) nrx -= 1;
				else nbx -= 1;
			}
			else if (cd == 2) {
				if (rcy < bcy) nry -= 1;
				else nby -= 1;
			}
			else if (cd == 3) {
				if (rcx < bcx) nbx += 1;
				else nrx += 1;
			}
		}
		rcx = nrx; rcy = nry;
		bcx = nbx; bcy = nby;
	}
}

void dfs(int cnt) {
	if (finish) return;
	if (cnt == 10) {
		move();
		return;
	}
	for (int i = 0; i < 4; i++) {
		order.push_back(i);
		dfs(cnt + 1);
		order.pop_back();
	}
}

int main() {
	cin >> row >> col;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'B' || arr[i][j] == 'R') {
				tmp.x = j;
				tmp.y = i;
				if (arr[i][j] == 'B') v[1].push_back(tmp);
				else v[0].push_back(tmp);
				arr[i][j] = '.';
			}
		}
	dfs(0);
	if (finish) cout << 1;
	else cout << 0;
	system("pause");
	return 0;
}

 

 

[DFS 진행중에 확인하기]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int row, col;
bool finish = false;
char arr[10][10];
struct info {
	int x, y;
};
info tmp;
vector<info> red;
vector<info> blue;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

void start(int cnt) {
	if (cnt > 10)
		return;
	int rx = red[0].x;
	int ry = red[0].y;
	int bx = blue[0].x;
	int by = blue[0].y;
	for (int i = 0; i < 4; i++) {
		bool r_finish = false, b_finish = false;
		int nrx = rx, nry = ry;
		int nbx = bx, nby = by;
		while (1) {
			if (arr[nry + dy[i]][nrx + dx[i]] == '.') {
				nry += dy[i];
				nrx += dx[i];
			}
			else if (arr[nry + dy[i]][nrx + dx[i]] == 'O') {
				r_finish = true;
				nry += dy[i];
				nrx += dx[i];
				break;
			}
			else if (arr[nry + dy[i]][nrx + dx[i]] == '#') break;
		}
		while (1) {
			if (arr[nby + dy[i]][nbx + dx[i]] == '.') {
				nby += dy[i];
				nbx += dx[i];
			}
			else if (arr[nby + dy[i]][nbx + dx[i]] == 'O') {
				b_finish = true;
				nby += dy[i];
				nbx += dx[i];
			}
			else if (arr[nby + dy[i]][nbx + dx[i]] == '#') break;
		}
		if (b_finish) continue;		//파란공이 어떻게든 들어가는 경우
		if (r_finish) {			//빨간공만 들어가는 경우
			finish = true;
			return;
		}
		if (nrx == nbx && nry == nby) {			//포개진 경우
			if (i == 0) {
				if (ry > by) 	nry += 1;	//빨간공이 밑에 있었던 경우
				else			nby += 1;
			}
			else if (i == 1) {
				if (rx > bx)	nbx -= 1;		//파란공이 더 왼쪽에서 시작한 경우
				else			nrx -= 1;
			}
			else if (i == 2) {
				if (ry > by)		nby -= 1;		//파란공이 더 위에서 시작
				else				nry -= 1;
			}
			else if (i == 3) {
				if (rx > bx)		nrx += 1;		//빨간공이 더 오른쪽에서 시작
				else				nbx += 1;
			}
		}
		red[0].x = nrx;
		red[0].y = nry;
		blue[0].x = nbx;
		blue[0].y = nby;
		start(cnt + 1);
		red[0].x = rx;
		red[0].y = ry;
		blue[0].x = bx;
		blue[0].y = by;
	}
}

int main() {
	cin >> row >> col;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'R') {
				tmp.x = j;
				tmp.y = i;
				red.push_back(tmp);
				arr[i][j] = '.';
			}
			else if (arr[i][j] == 'B') {
				tmp.x = j;
				tmp.y = i;
				blue.push_back(tmp);
				arr[i][j] = '.';
			}
		}
	start(1);
	if (finish) cout << 1;
	else cout << 0;
	return 0;
}