어흥
[백준 2886] 자리 전쟁 (C++) 본문
728x90
반응형
문제 링크: www.acmicpc.net/problem/2886
1. 주의할 점
- 우선순위큐를 사용하여 정렬을 한다(거리의 오름차순으로)
2. 구현
- 입력받을 때, 사람과 의자의 정보를 기억해놓는다
- 사람들과 의자사이의 거리를 구하여 구조체 형식(사람 번호, 의자 번호, 거리)으로 저장한 값을 우선순위큐에 담는다
- 우선순위큐에서 거리가 같으며, 아직 해당 사람이 의자에 앉지 않았고, 의자 또한 비어있다면 V 벡터에 의자 번호를 담는다. 동시에 사람이 의자를 앉았다는 표시를 한다(finished[pidx] = true)
- 거리가 다르고, V 벡터에 1개 이상 데이터가 쌓여있다면 Cal() 함수를 수행한다
- Cal() 함수는 V 벡터에서 원소를 비교하며 의자에 앉는 사람의 수를 1씩 증가시킨다. 그리고 사람의 수가 2가 되었다면, Result++을 통해 전쟁터의 수를 증가시킨다
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
int cidx, pidx, val;
};
struct cmp {
bool operator()(info &a, info &b) {
return a.val > b.val;
}
};
struct info2 {
int x, y;
};
info tmp;
info2 tmp2;
int row, col, result = 0;
char arr[100][100];
vector<info2> chair;
vector<info2> people;
int seated[10000]; //의자에 앉거나
bool finished[10000] = { false, }; //people
vector<int> v;
void cal() {
for (int i = 0; i < v.size(); i++) {
int cidx = v[i];
seated[cidx]++;
if (seated[cidx] == 2) result++;
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
priority_queue<info, vector<info>, cmp> pq;
cin >> row >> col;
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++) {
char c;
cin >> c;
arr[i][j] = c;
if (c == 'L') { //좌석
tmp2.x = j;
tmp2.y = i;
chair.push_back(tmp2);
}
else if (c == 'X') {
tmp2.x = j;
tmp2.y = i;
people.push_back(tmp2);
}
}
for (int i = 0; i < people.size(); i++) {
int px = people[i].x;
int py = people[i].y;
tmp.pidx = i;
for (int j = 0; j < chair.size(); j++) {
int cx = chair[j].x;
int cy = chair[j].y;
int dist = (cx - px)*(cx - px) + (cy - py)*(cy - py);
tmp.cidx = j;
tmp.val = dist;
pq.push(tmp);
}
}
int cidx = pq.top().cidx;
int pidx = pq.top().pidx;
int dist = pq.top().val;
v.push_back(cidx);
finished[pidx] = true;
pq.pop();
while (!pq.empty()) {
int nc = pq.top().cidx;
int np = pq.top().pidx;
int nd = pq.top().val;
pq.pop();
if (dist != nd) { //거리가 다르다면
dist = nd;
if (!v.empty()) {
cal();
v.clear();
}
}
if (seated[nc] == 0 && !finished[np]) { //해당 의자가 비었고, 이미 다른 의자에 앉은 사람이 아니라면
v.push_back(nc);
finished[np] = true;
}
}
if(!v.empty())
cal();
cout << result;
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 11451] 팩맨 (C++) (0) | 2020.09.28 |
---|---|
[백준 1495] 기타리스트 (C++) (0) | 2020.09.28 |
[백준 4358] 생태학 (C++) (2) | 2020.09.19 |
[백준 16947] 서울 지하철 2호선 (C++) (0) | 2020.09.15 |
[백준 2143] 두 배열의 합 (C++) (0) | 2020.09.08 |
Comments