[백준/BOJ] 백준 10218번 : Maze

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

10218번: Maze

 

빈칸인 경우 공이 있을 수 있는 위치이므로, 공이 있을 수 있는 빈칸의 위치들을 저장해 놓고 각 위치에서 왼쪽으로 기울기, 위쪽으로 기울기, 오른쪽으로 기울기, 아래쪽으로 기울기를 했을 때 경우를 확인해 가는 방식을 통해 문제를 해결했다.

기울이는 방향을 정할 때 이전에 움직였던 방향과 같은 방향으로 움직이는 것은 의미가 없으므로, 이전에 움직였던 방향으로는 또 다시 움직이지 않는 방식을 통해 확인하는 경우의 수를 줄여 문제를 해결했다.

 

코드

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

int tc;
int n, m;
vector<string> board;
int ball_cnt;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

void Pre() {
	board.clear();
}

//before_dir은 이전에 어떤 방향으로 움직였는지 나타내는데, 이유는 이전에 움직인 방향이랑 같은 방향으로 가면 같은 위치라 의미가 없기 때문이다
//이를 통해 움직일 경우의 수를 하나 더 줄일 수 있다
string Solve(vector<pair<int, int>> here_ball, int out_cnt, string maked, int before_dir) {

	if (maked.size() > 10) {
		return "XHAE";
	}

	//다 빠져 나갔는지 확인
	if (out_cnt == ball_cnt) {
		return maked;
	}

	string ret;
	vector<pair<int, int>> there_ball;
	int this_out_cnt;

	for (int dir = 0; dir < 4; dir++) {

		//지금 움직이는 방향이 이전에 움직였던 방향과 같다면 해당 방향으로는 움직이지 않는다
		//이를 통해 움직이는 경우의 수를 줄인다
		if (dir == before_dir) {
			continue;
		}

		there_ball.clear();
		this_out_cnt = 0; //해당 움직임으로 나가는 공의 개수

		for (int i = 0; i < here_ball.size(); i++) {

			if (board[here_ball[i].first][here_ball[i].second] == 'O') { //이미 빠져 나간 공일때
				continue;
			}

			pair<int, int> here = here_ball[i];
			pair<int, int> there = here;
			while (1) {
				there = make_pair(there.first + dxdy[dir][0], there.second + dxdy[dir][1]);
				if (board[there.first][there.second] == '#') { //움직이는 위치가 벽일때
					there = make_pair(there.first - dxdy[dir][0], there.second - dxdy[dir][1]);
					break;
				}
				else if (board[there.first][there.second] == 'O') { //움직이는 위치가 출구일때
					this_out_cnt++;
					break;
				}
			}
			there_ball.push_back(there);
		}

		if (dir == 0) { //현재 움직임이 왼쪽으로 기울기 일때
			ret = Solve(there_ball, out_cnt + this_out_cnt, maked + "L", dir);
		}

		else if (dir == 1) { //현재 움직임이 위쪽으로 기울기 일때
			ret = Solve(there_ball, out_cnt + this_out_cnt, maked + "U", dir);
		}

		else if (dir == 2) { //현재 움직임이 오른쪽으로 기울기 일때
			ret = Solve(there_ball, out_cnt + this_out_cnt, maked + "R", dir);
		}

		else { //현재 움직임이 아래쪽으로 기울기 일때
			ret = Solve(there_ball, out_cnt + this_out_cnt, maked + "D", dir);
		}

		if (ret != "XHAE") {
			return ret;
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> tc;

	for (int t = 0; t < tc; t++) {
		Pre();
		vector<pair<int, int>> ball;

		cin >> n >> m;

		for (int i = 0; i < n; i++) {
			string input;
			cin >> input;

			for (int j = 0; j < m; j++) {
				if (input[j] == '.') {
					ball.push_back(make_pair(i, j)); //공이 있을 수 있는 빈칸의 위치 저장
				}
			}

			board.push_back(input);
		}

		ball_cnt = ball.size();

		cout << Solve(ball, 0, "", -1) << "\n";
	}

	return 0;
}