[BOJ] 17244 아맞다우산

문제: www.acmicpc.net/problem/17244

 

 

<조건>

• 첫 번째 줄에는 집의 가로 길이 N과 세로 길이 M이 입력된다. (3 ≤ N, M ≤ 50)
  • "가로가 N"인 것을 주의하자!
• 두 번째 줄부터는 집의 구조가 예제 입력과 같이 주어진다.
  • 비어있는 곳은 '.'로 벽은 '#'로 입력된다. 경재 씨의 현재 위치는 S, 나가는 문의 위치는 E, 챙겨야 하는 물건은 종류에 상관없이 X로 입력된다.
• 챙겨야 하는 물건은 최대 5개까지 있을 수 있다.
• 집은 언제나 벽으로 둘러싸여 있고, 나가는 문은 언제나 하나이다.

 

문제 풀이:

• bfs로 문제를 해결했다.
• queue에 들어갈 데이터는 다음과 같다.
  • 현재 위치 (x, y) 값
  • 지금까지 습득한 아이템 정보
    • 각 아이템들을 map을 이용해 넘버링해준다.
      • item 번호 범위: [0, (item 개수-1)] 
      • ex) (x, y)에 있는 아이템의 번호는 1 -> itemList[make_pair(x,y)]=1
    • 습득한 아이템들을 bit mask를 이용해 저장한다
• 중복된 방문을 피하기 위해 visit 체크를 해준다.
  • 현재 위치(x, y)와 습득한 아이템 정보(bit mask)를 기준으로 visit 체크를 해준다.
• E에 도달했을 때, 모든 아이템을 다 가지고 있다면 결과를 갱신해준다.

 

소스 코드:

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;
int n, m,answer;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
char arr[52][52];
int visit[52][52][1<<6];
map<P, int> itemList;
P S, E;
struct state {
	int x;
	int y;
	int item;
};
void func() {
	queue<state> q;
	visit[S.first][S.second][0] = 1;
	q.push({ S.first,S.second,0 });

	while (!q.empty()) {
		int curX = q.front().x;
		int curY = q.front().y;
		int curItem = q.front().item;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int x = curX + dx[i];
			int y = curY + dy[i];
			if (arr[x][y] == '#' || visit[x][y][curItem]) continue;

			if (arr[x][y] == 'X') {
				int item = itemList[make_pair(x, y)];
				if (curItem & (1 << item)) {
					visit[x][y][curItem] = visit[curX][curY][curItem]+1;
					q.push({ x,y,curItem });
				}
				else {
					visit[x][y][curItem | (1 << item)] = visit[curX][curY][curItem] + 1;
					q.push({ x,y,curItem | (1 << item) });
				}
			}
			else if (arr[x][y] == 'E') {
				if (curItem == (1 << itemList.size()) - 1) {
					answer = min(answer, visit[curX][curY][curItem]);
				}
			}
			else {
				visit[x][y][curItem] = visit[curX][curY][curItem] + 1;
				q.push({ x,y,curItem });
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> m >> n;
	
	int itemNum = 0;
	answer = n * m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'S') S = make_pair(i, j);
			else if (arr[i][j] == 'E') E = make_pair(i, j);
			else if (arr[i][j] == 'X') {
				itemList[make_pair(i, j)] = itemNum++;
			}
		}
	}
	func();
	cout << answer << '\n';

	return 0;
}