[ 백준 BOJ ] 14595번 - 동방 프로젝트 (Large)(C++)

https://www.acmicpc.net/problem/14595

 

생각 흐름

• 핵심 포인트는 같은 곳은 다시 하지 부수지 않도록 하는 것이라고 생각했다.
• 따라서 정렬을 해주었는데, 정렬을 해주면 같은 곳에 대해 판별할 때 더 쉬울 거 같았다.
• 구현과 비슷하게 풀었다.
  • 벽에 대한 정보를 담고 있는 배열을 먼저 만들었다. 내부 데이터는 해당 벽을 허물 때의 정보로 예를 들어 {1, 5}와 같이 저장했다.
  • 이후 배열에 값을 넣을 시작 위치와 끝 위치를 찾아줬다. 아래와 같이 경우를 나누었다.
    
    • 왼쪽 위치의 배열값이 있을 때
      • 오른쪽 위치의 배열값이 있을 때
      • 오른쪽 위치의 배열값이 없을 때
    • 왼쪽 위취의 배열값이 없을 때
      • 오른쪽 위치의 배열값이 있을 때
      • 오른쪽 위치의 배열값이 없을 때
  • 이후 배열값이 없으면 방이 나뉘어진 것이므로 +1 해주는 연산을 해주었다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<pair<int,int>> m;
pair<int,int> ans[1500000];

bool comp(pair<int, int> a, pair<int, int> b){
    if(a.first==b.first){
        return a.second<b.second;
    }
    return a.first<b.first;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>N>>M;
    
    for(int i = 0; i<M; i++){
        int a,b;
        cin>>a>>b;
        
        m.emplace_back(a,b);
    }
    
    sort(m.begin(), m.end(), comp);
    
    for(int i = 0; i<m.size(); i++){
        pair<int, int> p = m[i];
        int start = p.first;
        int end = p.second;
        
        if(ans[p.first].first!=0){
            if(ans[p.first].second>=p.second) continue;
            if(ans[p.second-1].first!=0){
                if(ans[p.first]==ans[p.second-1]){
                    continue;
                }else if(ans[p.first].second<ans[p.second-1].first){
                    start=ans[p.first].second;
                    end = ans[p.second-1].first;
                }else if(ans[p.first].second>=ans[p.second-1].first){
                    continue;
                }
            }else{
                if(ans[p.first].second>=p.first)
                    start=ans[p.first].second;
            }
        }else{
            if(ans[p.second-1].first!=0){
                if(ans[p.second-1].first<=p.first) continue;
                if(p.second>=ans[p.second-1].first){
                    end=ans[p.second-1].first;
                }
            }
        }
        
        for(int j = start; j<end; j++){
            ans[j]=p;
        }
    }
    
    int answer = 1;
    
    for(int i = 1; i<N; i++){
        if(ans[i].first==0){
            answer++;
        }
    }
    
    cout<<answer<<endl;
    
    return 0;
}