BOJ 17244 아맞다우산 / C++

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

17244번: 아맞다우산

백준 온라인저지 17244번 아맞다우산 문제입니다.

 

아이디어

물건을 모두 찾아서 들어오는 문에서 나가는 문으로 나가야 하기때문에 물건을 숫자로 파싱하여 비트마스킹을 사용할 수 있게 했고, 최단 거리를 구하는 문제이기에 bfs를 이용하여 완전탐색으로 풀이 했습니다.

바로 전날 동일 유형문제를 풀어서 원트에 통과받았네요. :)

 

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

int room[MAX][MAX];
int way[MAX][MAX][(1 << 6)];
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 input() {
	cin >> m >> n;
	cnt = 0;
	char c;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> c;

			if (c == 'X')
				room[i][j] = ++cnt;

			else if (c == '#')
				room[i][j] = -1;
			else if (c == 'E')
				room[i][j] = 6;
			else if (c == 'S') {
				startPoint.y = i;
				startPoint.x = j;
				room[i][j] = 0;
			}

			else
				room[i][j] = 0;
		}
	}
}

void bfs() {
	queue < pair < pair<int, int> ,int> >q;
	q.push({ { startPoint.y, startPoint.x },{0} });
	way[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 (state == ((1 << cnt) - 1)) {
				//출입구라면
				if (room[ny][nx] == 6) {
					cout << way[y][x][state] << "\n";
					return;
				}
			}



			//물건이 있을때
			if (room[ny][nx]>0) {
				int newState = state | (1 << (room[ny][nx]-1));
				if (way[ny][nx][newState]) continue;
				way[ny][nx][newState] = way[y][x][state] + 1;
				q.push({ {ny, nx}, newState} );
			}
			if (way[ny][nx][state]) continue;
			way[ny][nx][state] = way[y][x][state] + 1;
			q.push({ {ny, nx}, state });
		}
	}
}

void solution() {
	bfs();
}

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