BOJ 4991 로봇 청소기/ C++

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

4991번: 로봇 청소기

백준 온라인저지 4991번 로봇 청소기문제입니다.

 

아이디어

더러운 칸이 최대 10개이기 때문에 더러운칸을 비트마스킹을 사용할 수 있게 숫자로 저장하고, 모든 더러운칸을 방문했을때 최소거리를 구하기 위해 bfs를 이용하여 완전탐색 하였습니다.

풀이 도중 더러운칸을 비트로 나타낸 state가 변경되었을때 newState를 사용하지 않아 고생을 좀 했네요

#include <iostream>
#include <queue>
#include<cstring>
#define MAX 21
using namespace std;

int room[MAX][MAX];
int cleanCnt[MAX][MAX][(1 << 11)];
int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int cnt;
int n, m;
struct point
{
	int x = 0;
	int y = 0;
};
point startPoint;

void bfs() {
	queue < pair < pair<int, int> ,int> >q;
	q.push({ { startPoint.y, startPoint.x },{0} });
	cleanCnt[startPoint.y][startPoint.x][0] = 1;
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int state = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i]; 
			int nx = x + dx[i];

			//범위 체크
			if (ny >= n || ny < 0 || nx >= m || nx < 0) continue;

			if (room[ny][nx] < 0) continue;
			
			//더러운 곳일때
			if (room[ny][nx]>0) {
				int newState = state | (1 << (room[ny][nx]-1));

				//더러운곳이 없다면
				if (newState == ((1 << cnt) - 1)) {
					cout<< cleanCnt[y][x][state]<<"\n";
					return;					
				}

				if (cleanCnt[ny][nx][newState]) continue;
				cleanCnt[ny][nx][newState] = cleanCnt[y][x][state] + 1;
				q.push({ {ny, nx}, newState} );
			}
			if (cleanCnt[ny][nx][state]) continue;
			cleanCnt[ny][nx][state] = cleanCnt[y][x][state] + 1;
			q.push({ {ny, nx}, state });
		}
	}
	
	
	cout << -1 << "\n";
}

void solution() {
	while (true) {
		cin >> m >> n;
		if (n == 0 && m == 0) break;
		cnt = 0;
		memset(cleanCnt, 0, sizeof(cleanCnt));
		memset(room, 0, sizeof(room));
		char c;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> c;
				
				if (c == '*')
					room[i][j] = ++cnt;

				else if (c == 'x')
					room[i][j] = -1;

				else if (c == 'o') {
					startPoint.y = i;
					startPoint.x = j;
					room[i][j] = 0;
				}
				else
					room[i][j] = 0;
			}
		}
		bfs();
	}
}

int main(void) {
	solution();
}