백준 1194번 _ 달이 차오른다, 가자.

www.acmicpc.net/problem/1194

1194번: 달이 차오른다, 가자.

---

bfs를 돌릴때 큐에 넣는 값들 처리를 미리하느냐 나중에 하느냐에 따라서 터지는 문제였다.

미리 안될만한 값들은 미리 처리해서 큐에 넣지 않게 하는게 중요한 문제다!!

---

전체코드 

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

using namespace std;

class BfsData {
public:
	int y;
	int x;
	int cnt;
	int key;
	BfsData(){}
	BfsData(int y_in, int x_in, int cnt_in, int key_in)
		:y(y_in), x(x_in), cnt(cnt_in), key(key_in){}
};

int N, M;
char map[50][50];
pair<int, int> startPos;
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
bool isVisit[50][50][1 << 6];

void printMap()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cout << map[i][j] << ' ';
		}
		cout << endl;
	}
}

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 >> map[i][j];
			if (map[i][j] == '0') 
			{
				startPos = make_pair(i, j);
				map[i][j] = '.';
			}
		}
	}
}

bool IsHaveKey(int key, char door)
{
	int ret = key & (1 << int(door - 'A'));

	if (ret != 0) 
		return true;
	return false;
}

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

	while (!que.empty())
	{
		int y = que.front().y;
		int x = que.front().x;
		int cnt = que.front().cnt;
		int havekey = que.front().key;
		que.pop();

		//도착했는지 확인
		if (map[y][x] == '1')
		{
			answer = cnt;
			break;
		}
		
		//이제 다음 곳으로 가기
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
	
			if (IsInRange(ny, nx) == false)
				continue;	

			if (isVisit[ny][nx][havekey] == true)
				continue;

			if (map[ny][nx] == '.' || map[ny][nx] == '1')
			{
				isVisit[ny][nx][havekey] = true;
				BfsData bfsData(ny, nx, cnt + 1, havekey);
				que.push(bfsData);			
			}
			else if ('a' <= map[ny][nx] && map[ny][nx] <= 'f')
			{
				int newKey = havekey | (1 << (int(map[ny][nx] - 'a')));
				isVisit[ny][nx][newKey] = true;
				BfsData bfsData(ny, nx, cnt + 1, newKey);
				que.push(bfsData);
			}
			else if ('A' <= map[ny][nx] && map[ny][nx] <= 'F')
			{
				if (IsHaveKey(havekey, map[ny][nx]) == true)
				{
					isVisit[ny][nx][havekey] = true;
					BfsData bfsData(ny, nx, cnt + 1, havekey);
					que.push(bfsData);
				}
			}
		}
	}
	cout << answer << endl;
}


int main()
{
	//cout << (1 << 0) << endl;

	Input();
	Bfs();
}