서랍장

Dark
블로그 이미지
책장/알고리즘

[백준-13460] 구슬 탈출 2

TERAJOO
|2021. 8. 12. 23:59

간단한 bfs 이지만 경우의 수가 매우 많은 귀찮은(?) 문제였다. 일단 시간제한은 2초 이지만 보드의 가로 세로가 최대 10 이므로 어떻게든 지지고 볶아도 시간 초과는 나지 않는 문제였다.

때문에 구현에만 정성을 쏟으면 된다. 로직은 다음과 같다.

  1. 위, 아래, 오른쪽, 왼쪽 4가지로 구분한다.
  2. 각 4가지별로 빨강이 앞에 있는 경우, 뒤에 있는 경우로 나눈다.
  3. 나눈 경우에 따라 while 문으로 벽이 나올 때까지 빨간 공과 파란 공을 움직인다. (이 때 서로 앞지르지는 못한다)

위의 1→2→3 을 반복하면 간단하게 문제가 풀린다. 이 때 시간 복잡도는 이전에 위로 움직인 경우 다음에 위로 움직이지 않게끔 하여 최대 3^10 정도가 나오게 된다. 대략 6만 정도가 나오게 되고, 각 케이스마다 1000줄씩 있다고 가정해도 6천만 정도의 넉넉한 복잡도가 나오게 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>

#define RED 2
#define BLUE 3
#define UP 100
#define DOWN 101
#define LEFT 102
#define RIGHT 103

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int n, m;
int check[12][12];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int dir[] = { UP, DOWN, LEFT, RIGHT };

int _min = 100;
void dfs(int _cnt, int _dir, pii _red, pii _blue) {
	if (_cnt > 10) return;
	
	if (_dir == UP) {
		if (_red.first < _blue.first) {
			// red 가 더 위에 있는 경우
			bool checkout = false;
			while (1) {
				if (check[_red.first - 1][_red.second] == -1) break;
				else if (check[_red.first - 1][_red.second] == 1) {
					checkout = true;
					break;
				}
				else {
					_red.first -= 1;
				}
			}
			while (1) {
				if (!checkout && _blue.first - 1 == _red.first && _blue.second == _red.second) break;
				else if (check[_blue.first - 1][_blue.second] == -1) break;
				else if (check[_blue.first - 1][_blue.second] == 1) {
					return;
				}
				else {
					_blue.first -= 1;
				}
			}
			if(checkout ) _min = min(_min, _cnt);
		}
		else {
			// blue 가 더 위에 있는 경우
			while (1) {
				if (check[_blue.first - 1][_blue.second] == -1) break;
				else if (check[_blue.first - 1][_blue.second] == 1) {
					return;
				}
				else {
					_blue.first -= 1;
				}
			}
			while (1) {
				if (_blue.first + 1 == _red.first && _blue.second == _red.second) break;
				if (check[_red.first - 1][_red.second] == -1) break;
				else if (check[_red.first - 1][_red.second] == 1) {
					_min = min(_min, _cnt);
					return;
				}
				else {
					_red.first -= 1;
				}
			}
		}
	}
	else if (_dir == DOWN) {
		if (_red.first < _blue.first) {
			// red 가 더 위에 잇는 경우
			
			while (1) {
				if (check[_blue.first + 1][_blue.second] == -1) break;
				else if (check[_blue.first + 1][_blue.second] == 1) {
					return;
				}
				else {
					_blue.first += 1;
				}
			}
			while (1) {
				if (_red.first + 1 == _blue.first && _blue.second == _red.second) break;
				else if (check[_red.first + 1][_red.second] == -1) break;
				else if (check[_red.first + 1][_red.second] == 1) {
					_min = min(_min, _cnt);
					return;
				}
				else {
					_red.first += 1;
				}
			}
		}
		else {
			// red가 밑에 있는 경우
			bool checkout = false;
			while (1) {
				if (check[_red.first + 1][_red.second] == -1) break;
				else if (check[_red.first + 1][_red.second] == 1) {
					checkout = true;
					break;
				}
				else _red.first += 1;
			}
			while (1) {
				if (!checkout && _blue.first + 1 == _red.first && _blue.second == _red.second) break;
				else if (check[_blue.first + 1][_blue.second] == -1) break;
				else if (check[_blue.first + 1][_blue.second] == 1) {
					return;
				}
				else 	_blue.first += 1;
			}
			if(checkout) _min = min(_min, _cnt);
		}
	}
	else if (_dir == LEFT) {
		if (_red.second > _blue.second) {
			// red 가 오른쪽에 있는 경우
			while (1) {
				if (check[_blue.first][_blue.second - 1] == -1) break;
				else if (check[_blue.first][_blue.second - 1] == 1) {
					return;
				}
				else 	_blue.second -= 1;
			}
			while (1) {
				if (_red.second - 1 == _blue.second && _blue.first == _red.first) break;
				else if (check[_red.first][_red.second - 1] == -1) break;
				else if (check[_red.first][_red.second - 1] == 1) {
					_min = min(_min, _cnt);
					return;
				}
				else 	_red.second -= 1;
			}
		}
		else {
			// red 가 왼쪽에 있는 경우
			bool checkout = false;
			while (1) {
				if (check[_red.first][_red.second - 1] == -1) break;
				else if (check[_red.first][_red.second - 1] == 1) {
					checkout = true;
					break;
				}
				else 	_red.second -= 1;
			}
			while (1) {
				if (!checkout && _blue.second - 1 == _red.second && _blue.first == _red.first) break;
				else if (check[_blue.first][_blue.second - 1] == -1) break;
				else if (check[_blue.first][_blue.second - 1] == 1) {
					return;
				}
				else 	_blue.second -= 1;
			}
			if(checkout) _min = min(_min, _cnt);
		}
	}
	else if (_dir == RIGHT) {
		if (_red.second > _blue.second) {
			// red 가 오른쪽에 있는 경우
			bool checkout = false;
			while (1) {
				if (check[_red.first][_red.second + 1] == -1) break;
				else if (check[_red.first][_red.second + 1] == 1) {
					checkout = true;
					break;
				}
				else 	_red.second += 1;
			}
			while (1) {
				if (!checkout && _blue.second + 1 == _red.second && _blue.first == _red.first) break;
				else if (check[_blue.first][_blue.second + 1] == -1) break;
				else if (check[_blue.first][_blue.second + 1] == 1) {
					return;
				}
				else 	_blue.second += 1;
			}
			if(checkout )_min = min(_min, _cnt);
		}
		else {
			// red 가 왼쪽에 있는 경우
			while (1) {
				if (check[_blue.first][_blue.second + 1] == -1) break;
				else if (check[_blue.first][_blue.second + 1] == 1) {
					return;
				}
				else 	_blue.second += 1;
			}
			while (1) {
				if (_red.second + 1 == _blue.second && _blue.first == _red.first) break;
				else if (check[_red.first][_red.second +1] == -1) break;
				else if (check[_red.first][_red.second + 1] == 1) {
					_min = min(_min, _cnt);
					return;
				}
				else 	_red.second += 1;
			}
		}
	}
	for (int i = 0; i < 4; i++) {
		if (dir[i] == _dir) continue;
		dfs(_cnt + 1, dir[i], _red, _blue);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	
	string row;
	pii red, blue;
	for (int i = 1; i <= n; i++) {
		cin >> row;
		for (int j = 1; j <= m; j++) {
			if (row.at(j-1) == '#') check[i][j] = -1;
			else if (row.at(j-1) == '.') check[i][j] = 0;
			else if (row.at(j-1) == 'O') check[i][j] = 1;
			else if (row.at(j-1) == 'R') 	red = { i,j };
			else if (row.at(j-1) == 'B')	blue = {i,j};
		}
	}

	// 기울이는 행동 자체를 탐색
	for (int i = 0; i < 4; i++) {
		dfs(1, dir[i], red, blue);
	}

	if (_min == 100) cout << -1;
	else cout << _min;

	return 0;
}

 

 

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

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

 

'책장 > 알고리즘' 카테고리의 다른 글

[백준-10943] 팰린드롬?  (0) 2021.08.15
[백준-2407] 조합  (0) 2021.08.13
[백준-1647] 도시 분할 계획  (0) 2021.08.12
[백준-1021] 회전하는 큐  (0) 2021.08.12

티스토리툴바