[백준 17244] 아맞다우산

비트마스킹 안쓰려고 버텼던 것의 결과물... ㅋㅋㅋㅋWA 4개 쌓고 굴복하였다....

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

17244번: 아맞다우산

#include <cstdio>
#include <queue>
int R, C;
char board[50 + 2][50 + 2];
int sx, sy;	// 출발지
int ex, ey;	// 도착지
int s_cnt;	// stuff 개수


struct _st
{
	int x, y;
	int move;
	int bit_num;	// 현재 어떤 물건을 가지고 이동하고 있는지	// 비트마스킹
};
std::queue<_st> Q;
int visited[50 + 2][50 + 2][1 << 6];	// 방문배열 visited[x][y][1 << X개수]
										// 비트마스킹을 이용하여 어떤 X들을 만나고 왔는지 알 수 있다. 
										// 같은 위치에 오더라도 다른 X를 만나고 오면 재방문 할 수 있다. 

void debug()
{
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			printf("%c", board[i][j]);
		}
		printf("\n");
	}
}


void input()
{
	scanf("%d %d", &C, &R);
	for (int i = 0; i < R; i++) {
		scanf("%s", &board[i]);
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 'X') {
				board[i][j] = s_cnt + '0';
				s_cnt++;
			}
			else if (board[i][j] == 'S') {
				sx = i;
				sy = j;
			}
			else if (board[i][j] == 'E') {
				ex = i;
				ey = j;
			}
		}
	}
}


int BFS()
{
	int dir_x[4] = { 0, 0 , 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	Q.push({ sx, sy, 0, 0 });	// 현재 아무 물건도 가지고 있지 않음
	visited[sx][sy][0] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		if (data.x == ex && data.y == ey && data.bit_num == (1 << s_cnt) - 1) return data.move;

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (board[nx][ny] == '#') continue;
			if (visited[nx][ny][data.bit_num]) continue;

			if (board[nx][ny] - '0' >= 0 && board[nx][ny] - '0' < 5) {	// 물건 5개 까지 있다. 
				int stuff = board[nx][ny] - '0';
				int nbit_num = data.bit_num | (1 << stuff);	// 추가한다
				if (visited[nx][ny][nbit_num] == 0) {		// 해당 물건을 가지고 도착한 적이 없는 경우
					Q.push({ nx, ny, data.move + 1, nbit_num });
					visited[nx][ny][nbit_num] = 1;
					continue;
				}
			}
			Q.push({ nx, ny, data.move + 1, data.bit_num });
			visited[nx][ny][data.bit_num] = 1;
		}
	}
	return  0;
}


int main()
{
	input();
	int ans = BFS();
	printf("%d\n", ans);
	return 0;
}

알면 간단한 비트마스킹.. 

1. 방문배열 할당은 visited[x][y][1 << 물건 X의 개수]

2. BFS 탐색 시 board[nx][ny] == 'X' 이라면(문제에서는 인덱싱하기 위해서 숫자로 다 바꿔줌)  

int nbit_num = data.bit_num | (1 << 인덱싱한 숫자) 해서 현재 있는 물건을 가지고 방문한 적이 있는지 체크하고 없으면 nbit_num을 큐에 삽입함

3. 다른 곳은 그냥 BFS처럼 큐에 삽입 후 방문처리 하면 됨