반응형
1944번: 복제 로봇
첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어
www.acmicpc.net
알고리즘 종류
- MST
- BFS
사고 과정
- 로봇은 시작점과 키 위치에서 원하는 개수 만큼 복제할 수 있다. 이는 노드에서 여러 간선으로 나갈 수 있다는 것을 의미한다. 복제된 로봇들이 키를 방문할 때 이동한 최소 거리를 구해야 한다. 이는 최소 스패닝 트리를 구하는 것이다.
1. 시작점과 키의 위치를 노드라고 하고, 노드들 간에 간선 비용을 구하기 위해서 BFS를 활용한다.
2. 구해진 간선을 가지고 크루스칼 알고리즘을 활용한다.
구현(C++)
|
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
|
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m;
int sy, sx;
int cnt = 0;
char mat[51][51];
int key_num[51][51];
int isVisited[51][51];
int parents[251];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
vector<pair<int, int> > nodes;
vector<pair<pair<int, int>, int> > edges;
bool isValid(int y, int x){
return (y>=0 && y<n) && (x>=0 && x<n);
}
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
return a.second < b.second;
}
// 간선 비용 구하기
void get_cost(int y, int x, int s){
memset(isVisited, 0, sizeof(isVisited));
queue<pair<int, int> > q;
q.push({y, x});
int dist = 1;
while(!q.empty()){
int size = q.size();
for(int i=0; i<size; i++){
y = q.front().first;
x = q.front().second;
isVisited[y][x] = 1;
q.pop();
for(int d=0; d<4; d++){
int ny = y + dir[d][0];
int nx = x + dir[d][1];
if(isVisited[ny][nx]) continue;
if(!isValid(ny, nx)) continue;
if(mat[ny][nx] == '1') continue;
isVisited[ny][nx] = 1;
q.push({ny, nx});
if(mat[ny][nx] == 'K'){
edges.push_back({{s, key_num[ny][nx]}, dist});
}
}
}
dist++;
}
}
int getParent(int x){
if(parents[x] == x) return x;
return parents[x] = getParent(parents[x]);
}
void unionParents(int a, int b){
a = getParent(a);
b = getParent(b);
if(a > b) parents[b] = a;
else parents[a] = b;
}
void kruskal(){
for(int i=1; i<=cnt; i++) parents[i] = i;
sort(edges.begin(), edges.end(), cmp);
int answer = 0;
for(int i=0; i<edges.size(); i++){
if(getParent(edges[i].first.first) != getParent(edges[i].first.second)){
unionParents(edges[i].first.first, edges[i].first.second);
answer += edges[i].second;
}
}
int p = getParent(1);
for(int i=2; i<=cnt; i++){
if(p != getParent(i)) {
cout << -1 << endl;
return;
}
}
cout << answer << endl;
}
void solution(){
// 간선의 비용을 구한다.
for(int i=0; i<nodes.size(); i++)
get_cost(nodes[i].first, nodes[i].second, i+1);
// 크루스칼 알고리즘
kruskal();
}
int main(void){
cin >> n >> m;
// 시작점과 키 위치를 노드로 정의한다.
for(int i=0; i<n; i++){
cin >> mat[i];
for(int j=0; j<n; j++){
if(mat[i][j] == 'S'){
mat[i][j] = 'K';
}
if(mat[i][j] == 'K'){
nodes.push_back({i,j});
key_num[i][j] = ++cnt;
}
}
}
solution();
}
|
cs |
시행착오
반응형