[Algorithm][C++] BOJ 4991 로봇 청소기

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

4991번: 로봇 청소기

 

풀이 핵심

1. BFS, DFS 활용

2. 로봇 청소기 위치 ('o'), 쓰레기 위치 ('*') 를 deque에 저장한다. (로봇 청소기의 위치가 가장 맨 앞[0]에 오게 하기 위해)

3. deque저장된 위치들을 배열에 저장 한다 (로봇 청소기 + 쓰레기 수 파악)

4. bfs를 이용해 로봇 청소기와 쓰레기, 각 쓰레기 사이의 최단 거리를 check 배열에 저장한다.

5. dfs를 이용해 최단 거리의 합을 구한다. (항상 로봇 청소기에서 시작해야 한다)

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <queue>
#include <deque>

using namespace std;
int T;
int R, C;
char map[20][20];
int check[11][11];
bool flag[11];
bool visited[20][20];
int ans;

struct POS { int r, c; };
deque<POS> tmp;
POS pos[11];
int pos_idx;

struct INFO {
	int r, c, dist;
};

int bfs(int sr, int sc, int er, int ec) {
	queue<INFO> q;
	bool visited[20][20] = { 0, };
	q.push({ sr,sc,0 });
	visited[sr][sc] = true;
	while (!q.empty()) {
		INFO cur = q.front();
		q.pop();
		if (cur.r == er && cur.c == ec) {
			return cur.dist;
		}
		const int dr[] = { 1,-1,0,0 };
		const int dc[] = { 0,0,-1,1 };
		for (int dir = 0; dir < 4; dir++) {
			int nr = cur.r + dr[dir];
			int nc = cur.c + dc[dir];
			if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
			if (visited[nr][nc] || map[nr][nc] == 'x') continue;
			q.push({ nr,nc,cur.dist + 1 });
			visited[nr][nc] = true;
		}
	}
	return -1;
}

void dfs(int idx, int sum, int cnt) {
	if (cnt == pos_idx - 1) {
		if (ans == -1) {
			ans = sum;
		}
		else if (ans > sum) ans = sum;
		return;
	}

	for (int i = 0; i < pos_idx; i++) {
		if (i == idx) continue;
		if (check[idx][i] == -1 || flag[i]) continue;
		flag[i] = true;
		dfs(i, sum + check[idx][i], cnt + 1);
		flag[i] = false;
	}
}

void solve() {
	for (int i = 0; i < pos_idx; i++) {
		for (int j = i + 1; j < pos_idx; j++) {
			check[i][j] = bfs(pos[i].r, pos[i].c, pos[j].r, pos[j].c);
			check[j][i] = check[i][j];
		}
	}
	flag[0] = true;
	dfs(0, 0, 0);
	printf("%d\n", ans);
}


int main() {
	while (1) {
		scanf("%d %d", &C, &R);
		if (!R && !C) break;
		tmp.clear();
		pos_idx = 0;
		memset(map, 0, sizeof(map));
		memset(visited, 0, sizeof(visited));
		memset(flag, 0, sizeof(flag));
		memset(check, 0, sizeof(check));
		ans = -1;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				scanf(" %c", &map[i][j]);
				if (map[i][j] == 'o') {
					tmp.push_front({ i,j });
				}
				else if (map[i][j] == '*') {
					tmp.push_back({ i,j });
				}
			}
		}
		while (!tmp.empty()) {
			pos[pos_idx++] = tmp.front();
			tmp.pop_front();
		}
		solve();
	}
	return 0;
}

 

아쉬운 점

굳이 deque 로봇 청소기 위치, 쓰레기 위치를 저장할 필요는 없을 것 같다

map, check의 memset은 필요 없을 것 같다 (flag도 flag[0] = false 만 추가해 주면 memset이 필요 없을 것 같다)

조금 더 코드를 다듬을 필요가 있는 것 같다.

단순히 bfs로 풀어야겠지라고 생각했지만 핵심은 dfs(순열)에 있었다.

쉽지 않은 문제였다.