#17244 아맞다우산

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

17244번: 아맞다우산

 

위 그림과 같이 입력값이 주어져 S에서 출발하여 물건X를 모두 수집하고 E로 도착하기 위한 최단 경로를 구하는 문제이다. 비트마스킹을 이용하여 visit[x][y][key(보유 키 현황)]배열을 생성하였고 bfs를 통해 구현하였다.

예를 들어 보유한 키가 0번 1번이면 00001 | 00010 = 00011 이 키 보유 현황이 되고 이때의 visit에서 bfs를 통해 새로운 키나 목적지를 찾아가게 된다.

 

 

	// #17244 아맞다우산
	#include <iostream>
	#include <queue>
	#define endl '\n'
	#include <cstring>
	using namespace std;
	char arr[52][52];
	int visit[51][51][1<<5];
	int n,m,keyn;
	int stx, sty, edx, edy;
	int dir[4][2] = { {1,0}, { 0,1 }, { -1,0 }, { 0,-1 } };
	typedef struct xy {
	int x, y,key;
	}xy;
	int bfs(int x,int y) {
	queue<xy> q;
	int key = 0;
	q.push({ x,y,key });
	visit[x][y][key] = true;
	int TIME = 0;
	while (!q.empty()) {
	int size = q.size();
	while (size--) {
	int fx = q.front().x, fy = q.front().y,fkey=q.front().key;
	q.pop();
	//cout << "fx " << fx << " fy " << fy << " fkey " << fkey << endl;
	if (arr[fx][fy] == 'E'&&fkey == (1 << keyn) - 1) {///열쇠를 모두 수집한 상태
	return TIME;
	}
	for (int d = 0; d < 4; d++) {
	int nx = fx + dir[d][0], ny = fy + dir[d][1], nkey = fkey;
	if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
	if (visit[nx][ny][nkey])continue;
	if (arr[nx][ny] == '#')continue;
	if ('0' <= arr[nx][ny] && arr[nx][ny] <= '4') {
	nkey |= (1 << (arr[nx][ny] - '0'));
	}
	visit[nx][ny][nkey] = true;
	q.push({ nx,ny,nkey });
	}
	}
	TIME++;
	}
	}
	int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	cin >> m >> n;
	keyn = 0;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	cin >> arr[i][j];
	if (arr[i][j] == 'S') {
	stx = i, sty = j;
	}
	else if (arr[i][j] == 'X') {
	arr[i][j] = keyn+'0';
	keyn++;
	}
	else if (arr[i][j] == 'E') {
	edx = i, edy = j;
	}
	}
	}
	cout<<bfs(stx, sty)<<endl;
	}

view raw [BOJ]17244.cpp hosted with ❤ by GitHub