백준 1175번 _ 배달

www.acmicpc.net/problem/1175

1175번: 배달

---

이 문제도 달이 차오른다, 가자. 문제랑 똑같다.

메모리가 터지지않게 최대한 안될만한 데이터들을 선처리해서 큐에 넣지 않게 하는게 중요한 문제다!

---

전체코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

class BfsData {
public:
	int y;
	int x;
	int dir;
	int time;
	int isDelivery;
	BfsData(){}
	BfsData(int y_in, int x_in, int dir_in, int time_in, int isDelivery_in)
		:y(y_in), x(x_in), dir(dir_in),time(time_in), isDelivery(isDelivery_in){}
};

int N, M;
char map[50][50];
pair<int, int> startPos;
bool isVisit[50][50][4][1 <<2];
pair<int, int> customerPos[2];

int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

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

void Input()
{
	cin >> N >> M;
	int idx = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 'S')
			{
				startPos = make_pair(i, j);
				map[i][j] = '.';
			}
			else if (map[i][j] == 'C')
			{
				customerPos[idx] = make_pair(i, j);
				idx++;
			}
		}
	}
}

int getIdxOfCustomer(int y, int x)
{
	int idx = -1;
	for (int i = 0; i < 2; i++)
	{
		if (customerPos[i].first == y && customerPos[i].second == x)
		{
			idx = i;
			break;
		}
	}
	return idx;
}

bool IsEndSituation(int isDelevery)
{
	if (isDelevery == 3)
		return true;
	return false;
}

void Bfs()
{
	int answer = -1;
	int isDelivery_in = 0;
	BfsData bfsInit(startPos.first, startPos.second, -1, 0, isDelivery_in);
	queue<BfsData> que;
	que.push(bfsInit);

	while (!que.empty())
	{
		int y = que.front().y;
		int x = que.front().x;
		int dir = que.front().dir;
		int time = que.front().time;
		int isDelevery = que.front().isDelivery;
		que.pop();

		//여기서 
		if (map[y][x] == 'C')
		{
			int idx = getIdxOfCustomer(y, x);
			isDelevery = (isDelevery | (1 << idx));
			if (IsEndSituation(isDelevery) == true)
			{
				answer = time;
				break;
			}
		}
		
		for (int i = 0; i < 4; i++)
		{
			// 방향이 같은가?
			if (dir == i)
				continue;

			int ny = y + dy[i];
			int nx = x + dx[i];

			// 범위를 넘는가?
			if (IsInRange(ny, nx) == false)
				continue;
			//장애물이 있는가?
			if (map[ny][nx] == '#')
				continue;
			//갔던 곳인가?
			if (isVisit[ny][nx][i][isDelevery] == true)
				continue;	
			
			if (map[ny][nx] == 'C' || map[ny][nx] == '.')
			{
				isVisit[ny][nx][i][isDelevery] = true;
				BfsData bfsData(ny, nx, i, time + 1, isDelevery);
				que.push(bfsData);
			}
		}
	}
	cout << answer << endl;
}

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