[c++] 백준 26656 점프킹

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

26656번: 점프킹

그래프 이론에 골드 1의 문제이기 때문에 문제를 풀기 위해 생각해야 할 것은 많지 않다.

그냥 생각나는 데로 구현하다 보면 풀리는 물제이다.

 

1. 탈출가능한 칸과 불가능한 칸의 분리 집합을 각각 만들어둔다.
2. 탈출가능한 분리집합 중 한 집합에서는 출구?(밖으로 나가게 되는 칸)이 무조건 한 칸이므로 한 칸만 조작하면 이 집합을 탈출 불가능하게 만들 수 있다. 이걸 역으로 생각하면 탈출 불가능한 집합도 한 칸의 조작으로 탈출 가능한 집합으로 바꿀 수 있다. 즉, 집합의 크기가 큰 순서대로 조작하면 문제에서 요구하는 최대, 최소를 구할 수 있다.

분리 집합을 구할 때는 유니온 파인드를 이용해 주었고,

탈출 가능과 불가능을 나누기 위해 맵을 사용하여 집합의 데이터를 저장, 탈출 여부 기록 후 각각의 벡터에 넣어주었다.

칸의 개수를 기준으로 내림차순 정렬하여 칸 조작 이전의(입력으로 주어진) 탈출 가능한 칸 개수를 조작하여 답을 구해준다.

#include<bits/stdc++.h>
using namespace std;
#define N 1010
typedef long long ll;
int n,m,k,arr[N][N],l[N][N];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int p[N*N];
vector<int> out_list;
int f(int x){
    if(x == p[x]) return x;
    return p[x] = f(p[x]);
}
map<char,int> idx;
void preprocess(){
    idx['R']=0; idx['L']=1; idx['D']=2; idx['U']=3;
    cin>>n>>m>>k;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            char c; cin>>c;
            l[i][j] = idx[c];
        }
    }
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin>>arr[i][j];
    for(int i=0; i<=n*m; i++)
        p[i]=i;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    preprocess();
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            int node = i*m+j;
            int ni = i+dx[l[i][j]]*arr[i][j];
            int nj = j+dy[l[i][j]]*arr[i][j];
            int nnode;
            if(0<=ni&&ni<n&&0<=nj&&nj<m){
                nnode = ni*m+nj;
                node = f(node);
                nnode= f(nnode);
                p[node] = nnode;
            }
            else{
                out_list.push_back(node);
            }
        }
    }
    map<int,int> room;
    map<int,int> isout;
    for(auto i : out_list)
        isout[f(i)] = 1;
    int OUT=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            int node = i*m+j;
            node = f(node);
            room[node]++;
            if(isout[node]) OUT++;
        }
    }
    vector<pair<int,int>> iv,ov;
    for(auto i : room){
        if(isout[i.first]) ov.push_back({i.second,i.first});
        else iv.push_back({i.second,i.first});
    }
    sort(iv.rbegin(),iv.rend());
    sort(ov.rbegin(),ov.rend());
    int MIN=OUT,MAX=OUT;
    for(int i=0; i<k; i++){
        if(i >= ov.size()) break;
        MIN -= ov[i].first;
    }
    for(int i=0; i<k; i++){
        if(i >= iv.size()) break;
        MAX += iv[i].first;
    }
    cout << MIN << ' ' << MAX;
    return 0;
}