백준 13460번 _ 구슬 탈출 2

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

13460번: 구슬 탈출 2

 

풀이방법

이 문제는 그냥 구슬을 굴리는 단순한 시뮬레이션이다.

하지만, 주의해야 할점이 몇가지 있다.

 

첫번째, 공끼리 붙었을때를 주의할것

 

 위의 그림과 같이 오른쪽으로 공을 굴린다고 하자 그렇다면 파란공이 먼저 굴러가고 빨간공이 굴러가야 우리가 원하는 동작이 나올것이다. 하지만 빨간공을 먼저 굴린다면 밑의 그림과 같은 문제점이 생길수있다. 언제 빨간공을 먼저굴려야하고 언제 파란공을 먼저 굴려야할까?

 

 이건 그냥 파란공 빨간색공의 좌표와 굴릴 방향을 계산해서 해줘도 무리는 없다.

 하지만, 구현하기 너무 귀찮아서 쉽게 할 방법 없을까 생각하다가 나온 방법이다.

 바로, 각 공을 같은 방향으로 2번씩 굴리는 것이다. 시간도 2초(약 2억개의 연산)으로 엄청 넉넉하므로 시간문제는 없다고 판단했다. 

 

두번째, 움직인 후의 공의 상태를 주의할것 

 

1. 빨간공 in, 파란공 in 은 fail

2. 빨간공 no in, 파란공 in 도 fail

3. 빨간공 in, 파란공 no in 은 sucess

4. 빨간공 no in, 파란공 no in은 계속 시뮬레이션 할것

 

이렇게 총 네가지 경우를 고려해서 짜야 오류가 생기지 않는다.

내 코드에서는 이 부분이다.

int checkMap(const vector<vector<char>>& map)
{
	bool BeRedball = false;
	bool BeBlueball = false;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] == 'R')
				BeRedball = true;
			else if (map[i][j] == 'B')
				BeBlueball = true;
		}
	}

	if (BeBlueball == false && BeRedball == true)
		return 0;
	if (BeBlueball == false && BeRedball == false)
		return 0;
	if (BeBlueball == true && BeRedball == true)
		return 1;
	if (BeBlueball == true && BeRedball == false)
		return 2;
}

 

이후에는 dfs를 쓰던, bfs를 쓰던 자유다. dfs를 쓸때는 중간중간 가지치기만 해주면 된다.

 

---

전체코드 ( 이번에 푼 코드, dfs로 품, 짧은 코드이나 시간면에선 느림 )

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <queue>

using namespace std;

vector<vector<char>> originalMap;
int N, M;
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };

void Input()
{
	cin >> N >> M;
	originalMap.resize(N + 2);
	for (int i = 0; i < N; i++)
		originalMap[i].resize(M + 2);
	char value;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> value;
			originalMap[i][j] = value;
		}
	}
}

pair<int, int>getBallPos(const vector<vector<char>>& map, char ballcolor)
{
	pair<int, int> ballpos = {0, 0};
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] == ballcolor)
			{
				return { i, j };
			}
		}
	}
	//map안에 공이 없으면 벽의 위치를 준거임
	return ballpos;
}

void ThisTimeisGoal(vector<vector<char>>& map, int dir, char ballcolor)
{
	char otherBallColor;
	if (ballcolor == 'R')
		otherBallColor = 'B';
	else
		otherBallColor = 'R';

	auto ballpositions = getBallPos(map, ballcolor);
	int PosY = ballpositions.first;
	int PosX = ballpositions.second;

	if (map[PosY][PosX] == '#')
		return;

	while (1)
	{
		int nPosY = PosY + dy[dir];
		int nPosX = PosX + dx[dir];

		if((map[nPosY][nPosX] == '#'))
			break;

		if (map[nPosY][nPosX] == 'O')
		{
			//공을 아예 지워버림
			map[PosY][PosX] = '.';
			break;
		}
		if (map[nPosY][nPosX] == otherBallColor)
			break;

		map[PosY][PosX] = '.';
		map[nPosY][nPosX] = ballcolor;
		PosY = nPosY;
		PosX = nPosX;
	}
}

//0, 1 , 2
int checkMap(const vector<vector<char>>& map)
{
	bool BeRedball = false;
	bool BeBlueball = false;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] == 'R')
				BeRedball = true;
			else if (map[i][j] == 'B')
				BeBlueball = true;
		}
	}

	if (BeBlueball == false && BeRedball == true)
		return 0;
	if (BeBlueball == false && BeRedball == false)
		return 0;
	if (BeBlueball == true && BeRedball == true)
		return 1;
	if (BeBlueball == true && BeRedball == false)
		return 2;
}

int answer = INT_MAX;
void dfs(vector<vector<char>>map, int dir, int cnt)
{
	if (cnt > 10 || cnt >= answer)
		return;

	ThisTimeisGoal(map, dir, 'R');
	ThisTimeisGoal(map, dir, 'B');
	ThisTimeisGoal(map, dir, 'R');
	ThisTimeisGoal(map, dir, 'B');
	int check = checkMap(map);
	if (check == 0)
		return;
	if (check == 2)
	{
		answer = min(answer, cnt);
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		if (i == dir)
			continue;
		dfs(map, i, cnt + 1);
	}
}

int main()
{
	Input();
	for (int i = 0; i < 4; i++)
		dfs(originalMap, i, 1);

	if (answer == INT_MAX)
		cout << -1;
	else
		cout << answer;
	return 0;
}

 

처음에 짠 코드 (bfs로 속도면에선 전자보다 훨씬 빠름, 약간의 하드코딩)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>

using namespace std;

class pos
{
public:
	int y;
	int x;

public:
	pos()
	{}
	pos(int y_in, int x_in) : y(y_in), x(x_in)
	{}
};

//touchOtherBall이 1일때가 다른공과 부딪친거임.
void Move(pos& redorBluePos, vector<vector<char>>& map, char blueOrRed, bool &holein, int YdirectionValue, int XdirectionValue)
{
	while (1)
	{
		//벽에 막혀있다면
		if (map[redorBluePos.y + YdirectionValue][redorBluePos.x + XdirectionValue] == '#')
			break;
		//갈수있다면 좌표를 움직이고 새로 맵을 그리기
		else if (map[redorBluePos.y + YdirectionValue][redorBluePos.x + XdirectionValue] == '.')
		{
			//원래있던 맵안의 B or R이->.으로
			map[redorBluePos.y][redorBluePos.x] = '.';

			//좌표를 옮기고 맵을 그에따라 바꾸기
			redorBluePos.x = redorBluePos.x + XdirectionValue;
			redorBluePos.y = redorBluePos.y + YdirectionValue;
			map[redorBluePos.y][redorBluePos.x] = blueOrRed;
		}
		//공이 들어가버리면?
		else if (map[redorBluePos.y + YdirectionValue][redorBluePos.x + XdirectionValue] == 'O')
		{
			holein = true;

			//원래있던 맵안의 B or R이 없어짐
			map[redorBluePos.y][redorBluePos.x] = '.';

			break;
		}
		//다른공에 부닥쳤을때 일단 break;
		else
		{
			break;
		}
	}
}


class bfsInformation
{
public:
	pos redpos;
	pos bluepos;
	vector<vector<char>> map;
	int cnt;
	int before;

	bfsInformation(pos redpos_in, pos bluepos_in, vector<vector<char>>map_in, int cnt_in, int before_in) 
		: redpos(redpos_in), bluepos(bluepos_in), map(map_in), cnt(cnt_in), before(before_in)
	{}
};

queue<bfsInformation> que;

int result = INT_MAX;
bool visit[11][11][11][11];

void BFS(pos redpos, pos bluepos, vector<vector<char>>map, int cnt, int before)
{
	//탈출조건 
	//cnt > 10
	if (cnt > 10)
		return;
	
	//상하좌우 탐색후 큐에 저장 
	
	//상
	if(map[redpos.y-1][redpos.x] != '#' || map[bluepos.y - 1][bluepos.x] != '#' && before!=1)
	{
		pos nextRed = redpos;
		pos nextBlue = bluepos;
		vector<vector<char>>nextmap = map;


		//혹시 공이 겹쳤을때 짜기 귀찮아서 두번해줌 ㅋㅋㅋ
		int XdirectionValue = 0;
		int YdirectionValue = -1;
		bool redholein = false;
		bool blueholein = false;
		Move(nextRed, nextmap, 'R', redholein, YdirectionValue, XdirectionValue);
		Move(nextBlue, nextmap, 'B', blueholein, YdirectionValue, XdirectionValue);
		Move(nextRed, nextmap, 'R', redholein, YdirectionValue, XdirectionValue);
		Move(nextBlue, nextmap, 'B', blueholein, YdirectionValue, XdirectionValue);
		
		if (blueholein == true)
		{ }
		else
		{
			if (redholein == true)
			{
				result = min(cnt, result);
				return;
			}
			if (visit[nextRed.y][nextRed.x][nextBlue.y][nextBlue.x] == false)
			{
				visit[nextRed.y][nextRed.x][nextBlue.y][nextBlue.x] = true;
				que.push(bfsInformation(nextRed, nextBlue, nextmap, cnt + 1, 1));
			}
		}
	}

	//하
	if (map[redpos.y + 1][redpos.x] != '#' || map[bluepos.y + 1][bluepos.x] != '#' && before != 2)
	{
		pos nextRed = redpos;
		pos nextBlue = bluepos;
		vector<vector<char>>nextmap = map;


		//혹시 공이 겹쳤을때 짜기 귀찮아서 두번해줌 ㅋㅋㅋ
		int XdirectionValue = 0;
		int YdirectionValue = +1;
		bool redholein = false;
		bool blueholein = false;
		Move(nextRed, nextmap, 'R', redholein, YdirectionValue, XdirectionValue);
		Move(nextBlue, nextmap, 'B', blueholein, YdirectionValue, XdirectionValue);
		Move(nextRed, nextmap, 'R', redholein, YdirectionValue, XdirectionValue);
		Move(nextBlue, nextmap, 'B', blueholein, YdirectionValue, XdirectionValue);
		if (blueholein == true)
		{
		}
		else
		{
			if (redholein == true)
			{
				result = min(cnt, result);
				return;
			}
			if (visit[nextRed.y][nextRed.x][nextBlue.y][nextBlue.x] == false)
			{
				visit[nextRed.y][nextRed.x][nextBlue.y][nextBlue.x] = true;
				que.push(bfsInformation(nextRed, nextBlue, nextmap, cnt + 1, 2));
			}
		}
	}

	//좌
	if (map[redpos.y][redpos.x-1] != '#' || map[bluepos.y][bluepos.x - 1] != '#' && before != 3)
	{
		pos nextRed = redpos;
		pos nextBlue = bluepos;
		vector<vector<char>>nextmap = map;


		//혹시 공이 겹쳤을때 짜기 귀찮아서 두번해줌 ㅋㅋㅋ
		int XdirectionValue = -1;
		int YdirectionValue = 0;
		bool redholein = false;
		bool blueholein = false;
		Move(nextRed, nextmap, 'R', redholein, YdirectionValue, XdirectionValue);
		Move(nextBlue, nextmap, 'B', blueholein, YdirectionValue, XdirectionValue);
		Move(nextRed, nextmap, 'R', redholein, YdirectionValue, XdirectionValue);
		Move(nextBlue, nextmap, 'B', blueholein, YdirectionValue, XdirectionValue);
		if (blueholein == true)
		{
		}
		else
		{
			if (redholein == true)
			{
				result = min(cnt, result);
				return;
			}
			if (visit[nextRed.y][nextRed.x][nextBlue.y][nextBlue.x] == false)
			{
				visit[nextRed.y][nextRed.x][nextBlue.y][nextBlue.x] = true;
				que.push(bfsInformation(nextRed, nextBlue, nextmap, cnt + 1, 3));
			}
		}
	}

	//우
	if (map[redpos.y][redpos.x+1] != '#' || map[bluepos.y][bluepos.x + 1] != '#' && before != 4)
	{
		pos nextRed = redpos;
		pos nextBlue = bluepos;
		vector<vector<char>>nextmap = map;

		//혹시 공이 겹쳤을때 짜기 귀찮아서 두번해줌 ㅋㅋㅋ
		int XdirectionValue = 1;
		int YdirectionValue = 0;
		bool redholein = false;
		bool blueholein = false;
		Move(nextRed, nextmap, 'R', redholein, YdirectionValue, XdirectionValue);
		Move(nextBlue, nextmap, 'B', blueholein, YdirectionValue, XdirectionValue);
		Move(nextRed, nextmap, 'R', redholein, YdirectionValue, XdirectionValue);
		Move(nextBlue, nextmap, 'B', blueholein, YdirectionValue, XdirectionValue);
		if (blueholein == true)
		{
		}
		else
		{
			if (redholein == true)
			{
				result = min(cnt, result);
				return;
			}
			if (visit[nextRed.y][nextRed.x][nextBlue.y][nextBlue.x] == false)
			{
				visit[nextRed.y][nextRed.x][nextBlue.y][nextBlue.x] = true;
				que.push(bfsInformation(nextRed, nextBlue, nextmap, cnt + 1, 4));
			}
		}
	}

	//큐에 있는 수들로 재귀
	if (!que.empty())
	{
		pos nextRed = que.front().redpos;
		pos nextBlue = que.front().bluepos;
		vector<vector<char>>nextmap = que.front().map;
		int nextCnt = que.front().cnt;
		int present = que.front().before;
		que.pop();
		BFS(nextRed, nextBlue, nextmap, nextCnt, present);
	}

}

int main()
{
	vector<vector<char>>map;
	int n, m;
	cin >> n >> m;

	//맵 만들기, R과 B 위치 저장
	pos redBallPos;
	pos blueBallPos;

	for (int i = 0; i < n; i++)
	{
		vector<char>vectmp;
		string strtemp;
		cin >> strtemp;
		for (int j = 0; j < (int)strtemp.size(); j++)
		{
			char temp;
			temp = strtemp[j];
			vectmp.push_back(temp);

			if (temp == 'R')
				redBallPos = pos(i, j);
			else if (temp == 'B')
				blueBallPos = pos(i, j);
		}
		map.push_back(vectmp);
	}

	BFS(redBallPos, blueBallPos, map, 1, 0);
	
	if (result == INT_MAX)
		result = -1;

	cout << result;

	return 0;
}

---

 

최근 코드

/*
시작 시간 : 10시 44분
종료 시간 : 11시 51분
소요 시간 : 1시간 7분

풀이방법 : bfs를 통해서 풀었습니다.
que에 board를 넣지 않고 board에 빨간공과 파란공을 set하고 이용후 다시 되돌려주게 했습니다.
*/
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

class BfsData
{
public:
	pair<int, int >redBallPos;
	pair<int, int >blueBallPos;
	int dir;
	int cnt;
	BfsData(){}
	BfsData(pair<int, int>redBallPos_in, pair<int, int>blueBallPos_in, int dir_in, int cnt_in)
		:redBallPos(redBallPos_in), blueBallPos(blueBallPos_in), dir(dir_in), cnt(cnt_in){}
};

int N, M;
char board[10][10];
pair<int, int> endPoint;
pair<int, int> redBallPosDefault;
pair<int, int> blueBallPosDefault;
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

void printBoard()
{
	for (int i = 0; i < N; i++)
	{	
		for (int j = 0; j < M; j++)
		{
			cout << board[i][j] << ' ';
		}
		cout << '\n';
	}
}

bool IsInRange(int y, int x)
{
	if (y >= 0 && y < N && x >= 0 && x < M)
		return true;
	return false;
}

void Input()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			cin >> board[i][j];
			if (board[i][j] == 'O')
				endPoint = make_pair(i, j);
			else if (board[i][j] == 'R')
				redBallPosDefault = make_pair(i, j);
			else if (board[i][j] == 'B')
				blueBallPosDefault = make_pair(i, j);
		}
}

void Move(pair<int, int>& pos, int dir)
{
	int y = pos.first;
	int x = pos.second;
	while (1)
	{
		int ny = y + dy[dir];
		int nx = x + dx[dir];
		
		if (IsInRange(ny, nx) == false || board[ny][nx] == '#')
			break;

		if (board[ny][nx] == 'R' || board[ny][nx] == 'B')
			break;

		//공이 들어가면 없앰
		if (board[ny][nx] == 'O')
		{
			board[y][x] = '.';
			break;
		}

		swap(board[y][x], board[ny][nx]);
		y = ny;
		x = nx;
	}
	pos.first = y;
	pos.second = x;
}

void SetBoard(char ballColor, pair<int, int>pos)
{
	board[pos.first][pos.second] = ballColor;
}

void ReturnBoard(char ballColor, pair<int, int>pos)
{
	board[pos.first][pos.second] = '.';
}

void bfs()
{
	int answer = -1;
	queue<BfsData> que;
	for (int dir = 0; dir < 4; dir++)
	{
		BfsData bfsInit(redBallPosDefault, blueBallPosDefault, dir, 1);
		que.push(bfsInit);
	}

	while (!que.empty())
	{
		pair<int, int> redPos = que.front().redBallPos;
		pair<int, int> bluePos = que.front().blueBallPos;
		int dir = que.front().dir;
		int cnt = que.front().cnt;
		que.pop();

		//10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
		if (cnt >= 11)
			break;

		//맵세팅
		SetBoard('R', redPos);
		SetBoard('B', bluePos);

		//cout << "움직이기 전" << '\n';
		//cout << "방향 : " << dir << '\n';
		//printBoard();
		//cout << '\n';

		//움직이기 : 연속 2번하는 이유는 겹치는 경우가 있기 때문
		Move(redPos, dir);
		Move(bluePos, dir);
		Move(redPos, dir);
		Move(bluePos, dir);

		//cout << "움직인 후" << '\n';
		//printBoard();
		//cout << '\n';

		//공이 위치에 있는지 확인
		//빨간구슬만 들어간 경우
		if (board[redPos.first][redPos.second] != 'R' && board[bluePos.first][bluePos.second] == 'B')
		{
			answer = cnt;
			break;
		}

		//파란구슬이 구멍에 들어간 경우
		if (board[bluePos.first][bluePos.second] != 'B')
		{
			//보드 원상복구
			ReturnBoard('R', redPos);
			ReturnBoard('B', bluePos);
			continue;
		}
		//보드 원상복구
		ReturnBoard('R', redPos);
		ReturnBoard('B', bluePos);

		//다음 큐 넣기
		for (int ndir = 0; ndir < 4; ndir++)
		{
			if (ndir == dir)
				continue;
			BfsData bfsData(redPos, bluePos, ndir, cnt + 1);
			que.push(bfsData);
		}
	}

	cout << answer << '\n';
}

int main()
{
	Input();
	bfs();
	return 0;
}

---

후기

이 문제는 예전에 어렵게 풀었었다가 다시한번 풀게된 문제인데 똑같이 까다로웠다. 

그리고 전에 짠 코드를 읽어봤는데 지금도 부족하지만 저때도 참 허접이다.

 

---

최근에 시험준비로 다시한번짰는데.. 그 뭐시냐 과외맨? 그거에 비하면 엄청 쉽게 느껴졌다.