[BOJ] 자리 전쟁 - Compy's Blog

자리 전쟁

TimeLimit	MemoryLimit	Condition	TAG
1s	128MB	(1 ≤ R, C ≤ 100)	Greedy

일단 생각보다 고려할게 많았던 문제였습니다.

한 관점에서만 가까운 것을 고르는 것은 문제가 있고, 전부 고려해서 제일 작은 것들을 미리 처리하고를 반복해서 없애는 방식을 채택했고, 처음에는 이거를 그냥 단순 visited 처리로 for문 돌렸는데 O((r*c)^3) 이정도 나오는 것을 보고서 음.. 안되겠군 하고서 그냥 처음에 생각했던 방법으로 접근했습니다. 그런데 이 과정에서 굉장히 많은 오류가 있고,,… 그냥 하던 코드 유지해야지.. 이러다가 시간을 날려 먹은 것 같네요.. 여러분ㄴ들은 꼭 아닌거 같다 싶으면 다시 짜보시길…

그러면 보통 금방 풀리더라구요

정답 코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
using ll = long long;
int r, c;

char board[101][101];
bool peopleVisited[10001];
int chairCount[10001];

ll getMinDistance(pair<int, int> a, pair<int, int> b){
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

void calculateWarfield(const vector<int>& chairIndices, int& result) {
    for(int idx : chairIndices) {
        chairCount[idx]++;
        if(chairCount[idx] == 2) {
            result++;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> r >> c;
    
    vector<pair<int, int>> chairs, people;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> board[i][j];
            if(board[i][j] == 'X') people.push_back({i, j});
            else if(board[i][j] == 'L') chairs.push_back({i, j});
        }
    }

    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
    
    for(int i = 0; i < people.size(); i++){
        for(int j = 0; j < chairs.size(); j++){
            ll dist = getMinDistance(people[i], chairs[j]);
            pq.push({dist, i, j});
        }
    }

    int result = 0;
    vector<int> currentChairIndices;
    ll currentDist = -1;

    while(!pq.empty()){
        auto [dist, personIdx, chairIdx] = pq.top();
        pq.pop();
        
        if(dist != currentDist){
            if(!currentChairIndices.empty()){
                calculateWarfield(currentChairIndices, result);
                currentChairIndices.clear();
            }
            currentDist = dist;
        }
        
        if(peopleVisited[personIdx] || chairCount[chairIdx] > 0) continue;
        
        currentChairIndices.push_back(chairIdx);
        peopleVisited[personIdx] = true;
    }
    
    if(!currentChairIndices.empty()) calculateWarfield(currentChairIndices, result);
    
    
    cout << result;
    
    return 0;
}