[G1] 백준 4991번 로봇 청소기 C++ 너비 우선 탐색, 비트마스

리뷰

 

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

딱 한글자 차이로 계속 헛짓을 했다...

 

 

전역 변수

• n : 방의 세로 크기를 저장할 변수
• m : 방의 가로 크기를 저장할 변수
• lst : 맵 정보를 저장할 배열
• bits : 더러운 칸 정보를 저장할 배열
• v : 방문 배열을 저장할 배열
• Pos : 시뮬레이션에 사용할 정보를 정의할 구조체 위치 x, y, 소요 시간 t, 치운 쓰레기 정보 b를 저장한다.
• dx, dy : 4방향 탐색을 위한 방향 배열

 

함수

1. bfs

int bfs(int d, int sx, int sy)

 

더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 함수

1. 매개 변수로 최대 쓰레기 정보 d, 시작 위치 sx, sy를 전달받는다.
2. Pos타입의 큐 q를 초기화 하고, 시작 위치와 초기 시간, 치운 쓰레기 정보를 0으로 push해준다.
3. 초기 위치와 치운 쓰레기 정보를 기준으로 방문 처리를 진행해 준다.
4. q가 빌 때 까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
5. 기저 조건으로 치운 쓰레기 정보가 2 ^ (쓰레기 개수 + 1) - 1일 경우 소요 시간을 리턴해 준다.
6. 4방향 탐색을 진행하고, 맵의 범위 안에 있으며 가구('x')가 아닐 경우 이동을 진행한다.
7. 이동 위치가 쓰레기라면 이미 치운 쓰레기인지 여부를 변수 nb를 통해 체크해 준다.
8. 치우지 않은 쓰레기라면 해당 쓰레기의 값bits[nx][ny] 만큼 치운 쓰레기 정보 nb에 더해준다.
9. 이동한 위치의 치운 쓰레기 정보가 방문처리 되어있다면 continue를 진행해 준다.
10. 방문 처리 되어있지 않으면 방문처리 후 q에 이동 위치, 소요 시간 + 1, 이동 후 치운 쓰레기 정보 push를 진행해 준다.
11. while루프가 종료될 때 까지 기저 조건에 도달하지 못하면 -1을 리턴해 준다.

 

2. print

void print(int x, int y, int t, int b)

 

디버깅용 함수

 

 

문제풀이

1. 정수형 타입 큐 resutls를 초기화 하고, 무한 루프를 개행한다.
2. 매 루프마다 m, n에 값을 입력하고, 두 값 모두 0이라면 break를 진행한다.
3. 변수 d, sx, sy를 0으로 초기화 하고 memset 메서드를 통해 v, bits를 0으로 초기화 해준다.
4. 맵 정보를 입력 받고, '*'가 입력되었을 경우 bits배열의 해당 위치에 2^d값을 저장해 준 뒤 d를 증가시킨다.
5. 'o'가 입력되었을 경우 sx, sy에 해당 위치를 저장하고 맵 정보를 '.'로 변경해 준다.
6. bfs함수에 매개변수로 d, sx, sy를 전달하고 리턴 받은 결과값을 results에 push해준다.
7. 무한 루프에서 빠져나왔을 경우 result에 저장된 값을 순차적으로 줄바꿈을 기준으로 출력해 준다.

 

트러블 슈팅

1. bfs 함수 내부에서 시작 지점을 방문처리 해 줄때 v[sx][sy][d]를 방문처리하여 계속 Fail을 받았다.
2. v[sx][sy][0]을 방문처리 해 주었더니 AC를 받았다, d가 1, 2, 4, 8일 때 엣지케이스가 발생한듯 하다.

 

참고 사항

없음

 

 

정답 코드

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

int n, m;
string lst[20];
int bits[20][20];
bool v[20][20][1024];
struct Pos {
	int x, y, t, b;
};
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void print(int x, int y, int t, int b) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (x == i && y == j) cout << 'o';
			else cout << lst[i][j];
		}
		cout << "\n";
	}
	cout << t << " " << b << "\n";
}

int bfs(int d, int sx, int sy) {
	queue<Pos> q;
	q.push({ sx, sy, 0, 0 });
	v[sx][sy][0] = 1;
	//cout << d << " " << pow(2, d) - 1 << "\n";

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t, cb = pos.b;
		if (cb == pow(2, d) - 1) return ct;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1, nb = cb;
			if (0 <= nx && nx < n && 0 <= ny && ny < m && lst[nx][ny] != 'x') {
				if (lst[nx][ny] == '*') {
					//cout << nb << " " << bits[nx][ny] << " " << (nb & bits[nx][ny]) << '\n';
					if ((nb & bits[nx][ny]) == 0) nb += bits[nx][ny];
				}
				if (v[nx][ny][nb]) continue;
				//print(nx, ny, nt, nb);
				v[nx][ny][nb] = 1;
				q.push({ nx, ny, nt, nb });
			}
		}
	}
	return -1;
}

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

	queue<int> results;
	while (1) {
		cin >> m >> n;
		if (!m && !n) break;
		int d = 0, sx = 0, sy = 0;
		memset(v, 0, sizeof(v));
		memset(bits, 0, sizeof(bits));
		for (int i = 0; i < n; ++i) {
			cin >> lst[i];
			for (int j = 0; j < m; ++j) {
				if (lst[i][j] == '*') {
					bits[i][j] = pow(2, d);
					d++;
				}
				if (lst[i][j] == 'o') {
					sx = i, sy = j;
					lst[i][j] = '.';
				}
			}
		}
		results.push(bfs(d, sx, sy));
	}
	while (!results.empty()) {
		cout << results.front() << "\n";
		results.pop();
	}
}