문제 URL : https://www.acmicpc.net/problem/4991
4991번: 로봇 청소기
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
www.acmicpc.net
문제 접근법 :
문제 조건을 잘보셔야합니다. 비트마스크 + bfs 문제인데
가로 세로가 최대 20이고 더러운것이 최대 10개밖에 없다고합니다.
이 10개를 이용해서 비트마스크를 이용해야하기 때문에
공간복잡도 최대가 20*20*2^10 까지 나온다는것을 깨달으면 문제는 어렵지않습니다.
더러운칸에 순서대로 번호를 부여해서 그칸을 방문할때마다 clean 변수에 or 처리를 해줍니다.
즉 경우의수가 2^(더러운칸)만큼 bfs를 전체 탐색하여 모두 방문했다면 clean 변수는 2^(더러운칸) -1 이 되면 전부 깨끗하게 청소한것이고 그것이 될수없다면 청소를 할수 없는 구간이 있는것입니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
#define vvvi v<vvi>
int n, m;
vvi board,dirty;
int sy, sx;
int cnt;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
void input() {
cin >> m >> n;
board= dirty = vvi(n, vi(m));
char c;
cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> c;
if (c == 'o') {
tie(sy, sx) = { i,j };
}
else if (c == 'x') {
board[i][j] = 1;
}
else if (c == '*') {
board[i][j] = 2;
dirty[i][j] = cnt++;//더러운칸 순서대로 번호부여
}
}
}
}
bool isrange(int y, int x) {
return 0 <= y && y < n && 0 <= x && x < m;
}
int bfs() {
vvvi check(n, vvi(m, vi(1 << cnt)));//더러운개수만큼 경우의수를 만듬
queue<tuple<int, int, int,int>> q;
q.push({ sy,sx,0,0 });
check[sy][sx][0] = 1;
while (!q.empty()) {
int y, x, clean, count;
tie(y, x, clean, count) = q.front();
q.pop();
if (board[y][x] == 2) {
clean |= 1 << dirty[y][x];
}
if (clean == (1 << cnt) - 1) {//전부 청소했는지
return count;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) &&board[ny][nx]!=1&& check[ny][nx][clean] == 0) {
q.push({ ny,nx,clean,count + 1 });
check[ny][nx][clean] = 1;
}
}
}
return -1;
}
void solve() {
cout << bfs() << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
while (true) {
input();
if (n == 0 && m == 0)break;
solve();
}
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등 어떤 질문이라도 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 13417 카드 문자열 (0) | 2021.11.25 |
|---|---|
| 백준 17089 세 친구 (0) | 2021.11.25 |
| 백준 1561 놀이 공원 (0) | 2021.11.17 |
| 백준 12763 지각하면 안 돼 (0) | 2021.11.12 |
| 백준 14725 개미굴 (0) | 2021.11.12 |
