백준 구슬탈출2

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

 

​

최단경로를 찾는 문제는 BFS로 구현해야한다.

​

그런데 이 문제에서 BFS로 구현하면서 각각의 노드에 대해서 기억해야 하는 정보가 많아서 난항을 겪었다.

​

BFS를 큐를 이용해서 구현하려고 했기 때문인데 생각해보니 큐에 기본 자료형을 넣을 생각만 하고 있었기 때문이다.

​

BFS에 쓰는 큐에 들어가는 자료형을 구조체로 직접 선언하여 필요한 정보를 각각의 노드마다 전부 저장하였다.

다음과 같이 저장했다.

 

 

 

 

 

 

 

 

 

 

BFS를 구현하는데 있어서 자기 마음껏, 재량껏 소스를 구현함에 따라 구현이 가능할 수도 있고 못할 수도 있었다.

 

전체 해답 소스는 다음과 같다.

 

#include<iostream>
#include<queue>

#define LEFT 0
#define DOWN 1
#define RIGHT 2
#define UP 3
using namespace std;

typedef struct Point
{
	int i;
	int j;
}point;

typedef struct myBFS
{
	int parent;
	int count;
	point Red;
	point Blue;
}bfs;

bool BFS(int direction, char map[][10], bfs* node, queue* pQue, point* pGoal)
{
	point tmpR, tmpB;
	tmpR.i = node->Red.i;	tmpR.j = node->Red.j;
	tmpB.i = node->Blue.i;	tmpB.j = node->Blue.j;
	int dstRed = 0, dstBlue = 0;
	bfs tmpNode;

	switch (direction)
	{
	case LEFT :
		for (int j = tmpB.j; map[node->Blue.i][j] != '#'; j--)
		{
			tmpB.j = j;
			dstBlue = node->Blue.j - tmpB.j;
			//파란공이 goal 에 들어가버리면 -1 출력
			if (pGoal->i == tmpB.i && pGoal->j == tmpB.j)
			{
				//cout << -1;
				return false;
			}
		}

		for (int j = tmpR.j; map[node->Red.i][j] != '#'; j--)
		{
			tmpR.j = j;
			dstRed = node->Red.j - tmpR.j;
			// 파란공이 goal에 안들어갔는데 빨간공이 들어간 경우
			if (pGoal->i == tmpR.i && pGoal->j == tmpR.j)
			{
				cout << node->count + 1 << endl;
				return true;
			}
		}
		// 공이 겹치는 경우
		if (tmpB.i == tmpR.i && tmpB.j == tmpR.j)
		{
			if (dstRed < dstBlue) tmpB.j++;
			if (dstRed > dstBlue) tmpR.j++;
		}
		
		tmpNode.parent = RIGHT;
		break;

	case RIGHT:
		for (int j = tmpB.j; map[node->Blue.i][j] != '#'; j++)
		{
			tmpB.j = j;
			dstBlue =  tmpB.j - node->Blue.j;
			//파란공이 goal 에 들어가버리면 -1 출력
			if (pGoal->i == tmpB.i && pGoal->j == tmpB.j)
			{
				//cout << -1;
				return false;
			}
		}

		for (int j = tmpR.j; map[node->Red.i][j] != '#'; j++)
		{
			tmpR.j = j;
			dstRed = tmpR.j - node->Red.j;
			// 파란공이 goal에 안들어갔는데 빨간공이 들어간 경우
			if (pGoal->i == tmpR.i && pGoal->j == tmpR.j)
			{
				cout << node->count + 1 << endl;
				return true;
			}
		}
		// 공이 겹치는 경우
		if (tmpB.i == tmpR.i && tmpB.j == tmpR.j)
		{
			if (dstRed < dstBlue) tmpB.j--;
			if (dstRed > dstBlue) tmpR.j--;
		}
		tmpNode.parent = LEFT;
		break;

	case DOWN:
		for (int i = tmpB.i; map[i][node->Blue.j] != '#'; i++)
		{
			tmpB.i = i;
			dstBlue = tmpB.i - node->Blue.i;
			//파란공이 goal 에 들어가버리면 -1 출력
			if (pGoal->i == tmpB.i && pGoal->j == tmpB.j)
			{
				//cout << -1;
				return false;
			}
		}

		for (int i = tmpR.i; map[i][node->Red.j] != '#'; i++)
		{
			tmpR.i = i;
			dstRed = tmpR.i - node->Red.i;
			// 파란공이 goal에 안들어갔는데 빨간공이 들어간 경우
			if (pGoal->i == tmpR.i && pGoal->j == tmpR.j)
			{
				cout << node->count + 1 << endl;
				return true;
			}
		}
		// 공이 겹치는 경우
		if (tmpB.i == tmpR.i && tmpB.j == tmpR.j)
		{
			if (dstRed < dstBlue) tmpB.i--;
			if (dstRed > dstBlue) tmpR.i--;
		}
		tmpNode.parent = UP;
		break;

	case UP:
		for (int i = tmpB.i; map[i][node->Blue.j] != '#'; i--)
		{
			tmpB.i = i;
			dstBlue = node->Blue.i - tmpB.i;
			//파란공이 goal 에 들어가버리면 -1 출력
			if (pGoal->i == tmpB.i && pGoal->j == tmpB.j)
			{
				//cout << -1;
				return false;
			}
		}

		for (int i = tmpR.i; map[i][node->Red.j] != '#'; i--)
		{
			tmpR.i = i;
			dstRed = node->Red.i - tmpR.i;
			// 파란공이 goal에 안들어갔는데 빨간공이 들어간 경우
			if (pGoal->i == tmpR.i && pGoal->j == tmpR.j)
			{
				cout << node->count + 1 << endl;
				return true;
			}
		}
		// 공이 겹치는 경우
		if (tmpB.i == tmpR.i && tmpB.j == tmpR.j)
		{
			if (dstRed < dstBlue) tmpB.i++;
			if (dstRed > dstBlue) tmpR.i++;
		}
		tmpNode.parent = DOWN;
		break;

	default:
		break;
	}//switch

	//하나라도 움직였으면 움직인 상태를 큐에 업데이트하자
	if (node->Red.i != tmpR.i || node->Red.j != tmpR.j
		|| node->Blue.i != tmpB.i || node->Blue.j != tmpB.j)
	{
		
		tmpNode.Red.i = tmpR.i; tmpNode.Red.j = tmpR.j;
		tmpNode.Blue.i = tmpB.i; tmpNode.Blue.j = tmpB.j;
		//tmpNode.parent = direction;
		tmpNode.count = node->count + 1;

		pQue->push(tmpNode);
	}

	return false;

}
int main()
{
	queue que;
	int N, M;
	char cMap[10][10] = {0,};
	bfs stNode;
	point goal;

	//입력을 받는다
	cin >> N >> M;
	//scanf("%d", &N);
	//scanf("%d", &M);
	for(int i = 0 ; i < N ; i++)
		for (int j = 0; j < M; j++)
		{
			cin >> cMap[i][j];
			//scanf("%c", &cMap[i][j]);
			if (cMap[i][j] == 'R')
			{
				stNode.Red.i = i;
				stNode.Red.j = j;
			}
			else if (cMap[i][j] == 'B')
			{
				stNode.Blue.i = i;
				stNode.Blue.j = j;
			}
			else if (cMap[i][j] == 'O')
			{
				goal.i = i;
				goal.j = j;
			}
		}
	//최초의 정보로 구조체를 만들자.
	stNode.count = 0;
	stNode.parent = 9;	//없는 방향 초기화.

	// 최초의 구조체를 que.push 한다.
	que.push(stNode);

	while (!que.empty())
	{
		stNode = que.front(); que.pop();
		if (stNode.count < 10)
		{
			// i 는 direction 으로 쓰임
			// 부모와 같은 방향으로는 탐색하지 않는다.
			for (int i = 0; i < 4; i++)	
			{
				if (i != stNode.parent)
				{
					if (BFS(i, cMap, &stNode, &que, &goal)) return 0;
					else continue;
				}
			}
		}
	}	//while

	cout << -1 << endl;
	return 0;
}