[백준/C++] 4991 로봇 청소기

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

 

코드

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

#define MAX 21
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);
typedef pair<pair<int, int>, pair<int, int>> pi;

int w, h, dirty = 0, rx, ry;
int arr[MAX][MAX], dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
bool visit[MAX][MAX][1 << 11];
string s;

void init() {
	dirty = 0;
	memset(visit, false, sizeof(visit));
	memset(arr, 0, sizeof(arr));
}

int bfs() {
	queue<pi> q;
	q.push({ {rx,ry},{0, 0} });

	while (!q.empty()) {
		int nx = q.front().first.first;
		int ny = q.front().first.second;

		int cnt = q.front().second.first;
		int find = q.front().second.second;

		q.pop();

		if (find == (1 << dirty) - 1) 
			return cnt;

		for (int i = 0, tfind; i < 4; i++) {
			tfind = find;
			int gx = nx + dx[i];
			int gy = ny + dy[i];

			if (gx >= 0 && gx < h && gy >= 0 && gy < w && arr[gx][gy] != -1) {
				if (arr[gx][gy] > 0) {
					tfind |= (1 << (arr[gx][gy] - 1));
				}

				if (!visit[gx][gy][tfind]) {
					visit[gx][gy][tfind] = true;
					q.push({ {gx, gy}, {cnt + 1, tfind} });
				}
			}
		}
	}
	return -1;
}

int main() {
	FASTIO;
	
	while (true) {
		cin >> w >> h;
		if (w == 0 && h == 0) break;
		init();

		for (int i = 0; i < h; i++) {
			cin >> s;
			for (int j = 0; j < w; j++) {
				if (s[j] == '.') arr[i][j] = 0;
				else if (s[j] == 'x') arr[i][j] = -1;
				else if (s[j] == 'o') {
					arr[i][j] = 0;
					rx = i, ry = j;
				}
				else {
					arr[i][j] = dirty + 1;
					dirty++;
				}
			}
		}
		cout << bfs() << "\n";
	}
	return 0;
}

 

설명

먼저 입력을 받고 저는 제가 사용하기 편하도록 변경해주었습니다. 

• 깨끗한 칸, 로봇 청소기의 시작 위치 = 0
• 가구 = -1
• 더러운 칸 = 1 이상의 정수

bfs를 돌면 되는데 더러운 칸의 방문 관리를 위해서 비트마스킹을 이용했습니다. 

 

느낀 점

1194번 문제를 풀었다면 어렵지 않게 풀 수 있는 문제인 것 같습니다. memset을 썼는데 헤더 파일을 까먹어서 한 번 컴파일에러로 틀렸습니다.