[G2] 백준 17244번 아맞다우산 C++ 너비 우선 탐색, 비트마스킹

리뷰

 

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

BFS + 비트마스킹을 통해 물건 챙긴 상태를 분기처리하여 탐색하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n, m : 맵의 세로/가로 길이를 저장할 변수
• idx : 물건의 번호를 식별하고, 개수를 저장할 변수
• sx, sy : 시작 위치의 x, y좌표를 저장하기 위한 변수
• ex, ey : 도착 위치의 x, y좌표를 저장하기 위한 변수
• lst : 맵 정보를 저장하기 위한 2차원 배열
• v : 맵 정보, 물건을 찾은 상태를 방문 체크하기 위한 3차원 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 현재 위치와 누적 소요 시간, 찾은 물건 정보를 정의할 구조체

 

함수

1. bfs

int bfs() {
	queue<Pos> q;
	q.push({ sx, sy, 0, 0 });
	v[0][sx][sy] = true;
	int tar = (1 << idx) - 1;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.cx, cy = pos.cy, ct = pos.ct, cc = pos.cc;
		//cout << cx << " " << cy << " " << ct << " " << cc << "\n";
		if (cx == ex && cy == ey && cc == tar) return ct;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1, nc = cc;

			if (0 <= nx && nx < n && 0 <= ny && ny < m && lst[nx][ny] != -1) {
				if (lst[nx][ny]) nc |= 1 << lst[nx][ny] - 1;

				if (v[nc][nx][ny]) continue;
				v[nc][nx][ny] = true;
				q.push({ nx, ny, nt, nc });
			}
		}
	}
	return -1;
}

 

너비 우선 탐색을 통해 시작 위치에서 출발하여 모든 물건을 찾고 도착 위치에 도달하는 최단 시간을 구하기 위한 함수

 

 

문제풀이

1. m, n값을 입력 받고, n*m크기의 맵 정보를 입력 받는다.
2. lst배열에 맵 정보가 '#'라면 -1, 'X'라면 ++idx, 'S', 'E'라면 sx, sy, ex, ey에 시작 및 도착 위치 좌표를 저장한다.
3. bfs함수를 호출하여 Pos타입의 큐 q를 초기화 하고, 초기값으로 sx, sy, 0, 0을 push해준다.
4. 시작 위치 v[0][sx][sy]를 방문처리하고, 변수 tar에 모든 물품을 찾은 비트값을 저장해 준다. (1 << idx) - 1
5. q가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 꺼내 변수 cx, cy, ct, cc에 파싱해 준다.
6. 기저 조건으로 현재 위치가 도착지점이고 모든 물품을 찾은 상태라면 ct를 리턴해 준다.
7. 4방향 탐색을 진행하고, 변수 nx, ny, nt, nc에 이동 후 정보를 각각 저장해 준다.
8. 이동한 위치가 맵의 범위 내에 있으며 벽이 아닐 경우 이동을 진행해 준다.
9. 만약 이동한 위치에 물건이 존재한다면 nc에 물건의 번호 번째의 비트를 or연산 처리해 준다.
10. v[nc][nx][ny]에 방문처리가 되어있지 않다면 방문처리 후 q에 nx, ny, nt, nc를 push 해준다.
11. 기저 조건에 도달할 경우 bfs함수의 리턴값을 출력해 준다.

 

트러블 슈팅

1. 디버깅에 사용한 개행문자를 주석처리 해주지 않아 출력 형식이 잘못되었다는 Fail을 받았다.
2. 디버깅에 사용한 출력문들을 모두 주석처리 해주어 AC를 받았다.

 

참고 사항

1. 챙겨야 하는 물건은 최대 5개까지 있을 수 있다.
2. 모든 물건을 챙길 수 없는 경우는 주어지지 않는다.

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;

const int N = 50;
int n, m, idx, sx, sy, ex, ey;
int lst[N][N];
bool v[1 << 5][N][N];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos {
	int cx, cy, ct, cc;
};

int bfs() {
	queue<Pos> q;
	q.push({ sx, sy, 0, 0 });
	v[0][sx][sy] = true;
	int tar = (1 << idx) - 1;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.cx, cy = pos.cy, ct = pos.ct, cc = pos.cc;
		//cout << cx << " " << cy << " " << ct << " " << cc << "\n";
		if (cx == ex && cy == ey && cc == tar) return ct;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1, nc = cc;

			if (0 <= nx && nx < n && 0 <= ny && ny < m && lst[nx][ny] != -1) {
				if (lst[nx][ny]) nc |= 1 << lst[nx][ny] - 1;

				if (v[nc][nx][ny]) continue;
				v[nc][nx][ny] = true;
				q.push({ nx, ny, nt, nc });
			}
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> m >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			char c; cin >> c;
			if (c == '#') lst[i][j] = -1;
			else if (c == 'X') lst[i][j] = ++idx;
			else if (c == 'S') sx = i, sy = j;
			else if (c == 'E') ex = i, ey = j;
			//cout << lst[i][j] << " ";
		}
		//cout << "\n";
	}

	cout << bfs();
}