백준알고리즘

(4991) 로봇 청소기

먼지의삶 2019. 10. 1. 22:49

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<iostream>
#include<queue>
#include<vector>
#include<utility>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
struct Pair {
    int x, y, v;
    Pair(int x, int y, int v) {
        this->x = x;
        this->y = y;
        this->v = v;
    }
};
class Edge {
public:
    int node[2];
    int value;
    Edge(int x, int y, int v) {
        this->node[0] = x;
        this->node[1] = y;
        this->value = v;
    }
    bool operator<(Edge& edge) {
        return this->value < edge.value;
    }
};
int c, r,sx,sy;
char map[21][21];
int posi[21][21];
bool d[21][21][11];
bool so[15];
int dist[21][21][11];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int ans=987654321;
 
vector<pair<int, int> > v;
vector<Edge> poe;
int os = 0;
void bfs(int x, int y, int node1) {
    queue<pair<int, int> > q;
    q.push({ x,y });
    d[x][y][node1] = true;
    while (!q.empty()) {
        x = q.front().first; y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i]; int ny = y + dy[i];
            if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
                if (d[nx][ny][node1] == false && map[nx][ny] != 'x') {
                    d[nx][ny][node1] = true;
                    dist[nx][ny][node1] = dist[x][y][node1] + 1;
                    q.push({ nx,ny });
                    if (map[nx][ny] == '*' || map[nx][ny] == 'o') {
                        poe.push_back(Edge(node1, posi[nx][ny], dist[nx][ny][node1]));
                        os++;
                    }
                }
            }
        }
    }
}
 
 
void dfs(int x,int start, int point, int cnt,int sum) {
    if (ans < sum) return;
    if (cnt == point-1) {
        //cout << "HELLO" << endl;
        if (ans > sum) ans = sum;
        return;
    }
    else {
        //cout << x << '\n';
        for (int i = 0; i < poe.size(); i++) {
            if (poe[i].node[1] == start) continue;
            if(poe[i].node[0] == x){
                if (so[poe[i].node[1]] == false) {
                    so[poe[i].node[1]] = true;
                    dfs(poe[i].node[1], start, point, cnt + 1, sum + poe[i].value);
                    so[poe[i].node[1]] = false;
                }
            }
        }
    }
    
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while (true) {
        cin >> c >> r;
        if (c == 0 && r == 0) break;
        ans = 987654321;
        int point = 2;
        v.clear();
        poe.clear();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                cin >> map[i][j];
                if (map[i][j] == 'o') {
                    posi[i][j] = 1;
                    sx = i; sy = j;
                }if (map[i][j] == '*') {
                    posi[i][j] = point;
                    v.push_back({ i,j });
                    point++;
                }
            }
        }
        os = 1;
        bfs(sx, sy, posi[sx][sy]);
        if (os != point - 1)
            cout << -1 << '\n';
        else {
            for (int i = 0; i < v.size(); i++) {
                bfs(v[i].first, v[i].second, posi[v[i].first][v[i].second]);
            }
            so[1] = true;
            dfs(1, 1, point, 1, 0);
            cout << ans << '\n';
            
        }
        
            
        memset(so, false, sizeof(so));
        memset(dist, 0, sizeof(dist));
        memset(d, false, sizeof(d));
 
 
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
  

처음에, 최소스패닝 트리를써도 괜찮은 문제라고 생각했다.

하지만, 최소경로로 잇고나서, 다시 돌아오는길을 선택할수 없기에, 왔다가 갔다가 하는 행위를 할수없었고,

최소스패닝 트리를 쓰는 문제가 아닌 완전탐색 문제다.