BOJ1194 달이 차오른다, 가자. /C++

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

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

백준 온라인 저지 1194번 달이 차오른다, 가자. 문제입니다.

 

풀이과정

비트마스킹과 BFS를 이용하여 풀이하였는데, 사실 노드의 상태를 비트로 표현하여 탐색하는 문제는 이제 어느정도 익숙해서 풀만해서 풀이자체는 어렵지 않았습니다. 그런데 상태 관리하는 부분과 메모리를 신경쓰지 못해서 고생을 많이 했네요. 상태관리하는 부분은 for문이 돌면서 열쇠가 없이 방문해야하는 state일때 이전의 state를 그대로 사용하여 열쇠가 있는 상태로 탐색을 하는 바람에 테스트케이스보다 더 빨리 탈출하는 경우가 발생하여 틀렸었고, 아래보면 처참한 메모리 초과 내역이 있습니다... 큐가 무한으로 쌓이는 케이스가 발생했을 수 있는 경우를 찾다가 문제를 다시 들여다 보니 메모리는 128MB까진데 int 4개짜리 큐를 돌리다보니 메모리 초과가 났을것으로 판단하여 방문검사를 큐에 우선 넣고 조건문으로 걸러내는 방식에서 넣기전 확인하여 메모리 오버되지 않게 처리 하고 나서야 성공을 받았습니다.

정리 : 상태관리와 메모리 초과를 주의하자

 

#include<iostream>
#include<queue>
#include <string>
using namespace std;

int n, m;
struct point
{
	int y = 0;
	int x = 0;
};
char arr[50][50];
point start;
bool visited[50][50][(1 << 6)];

int ny[4] = { 0,0,-1,1 };
int nx[4] = { 1,-1,0,0 };

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			arr[i][j] = s[j];
			if (arr[i][j] == '0') {
				start.y = i;
				start.x = j;
			}
		}
	}
}


int bfs(int sY, int sX) {
	//<<y,x>,<cnt,state>>
	queue<pair<pair<int, int>, pair<int, int>> > q;
	q.push({ {sY,sX},{0,0} });
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int cnt = q.front().second.first;
		int state = q.front().second.second;
		q.pop();
		if (arr[y][x] == '1') return cnt;
		for (int i = 0; i < 4; i++) {
			int dy = y + ny[i];
			int dx = x + nx[i];
			//범위 체크
			if (dy >= n || dy < 0 || dx >= m || dx < 0) continue;
			//벽 체크
			if (arr[dy][dx] == '#') continue;
			//열쇠 획득
			if (arr[dy][dx] >= 'a' && arr[dy][dx] <= 'f') {
				//state를 아래와 같이 가져가면 for문을 돌면서 열쇠가 없는 상태로 방문을 열어야할때 이전 for문에 의해 열쇠가 있는 경우가 생김
				//state = state | (1 << (arr[dy][dx] - 'a'));
				int new_state = state | (1 << (arr[dy][dx] - 'a'));
				if (visited[dy][dx][new_state]) continue;
				visited[dy][dx][new_state] = true;
				q.push({ { dy,dx }, { cnt + 1,new_state } });
				continue;
			}
			//열쇠 체크
			else if (arr[dy][dx] >= 'A' && arr[dy][dx] <= 'F') {
				if ((state &  (1 << (arr[dy][dx] - 'A'))) == 0)
					continue;
			}
			if (visited[dy][dx][state]) continue;
			visited[dy][dx][state] = true;
			q.push({ { dy,dx }, { cnt + 1,state } });
		}
	}
	return -1;
}

void solution() {
	cout << bfs(start.y, start.x);
}

int main(void) {
	input();
	solution();
}

 

처참한 메모리초과...