PS Diary #4

 

 

 

 

 

 

 

 

USACO 2024 December. 2D Conveyor Belt

dfs, bfs, offline query

 $N \leq 10^3, Q\leq 10^5$일 때 $N\times N$ 격자에서 처리해야하므로 처음에 $O(N^2)$이하로 unusable한 conveyor belt들을 모두 계산해두고 $Q$개의 쿼리동안 $O(1)$안에 답을 계산해 출력하는 $O(N^2 + Q)$를 목표로 생각했다. 그래서 먼저 dfs를 잘 이용해 최종상태에서 unusable여부를 미리 계산을 해두었다. 계산을 해두고 보니 처음 상태에서 추가를 하는 것보다 최종상태에서 하나씩 빼는 것이 더 쉬울 것이라고 생각했다. 하나를 뺄 때 그 칸이 unusable->usable로 바뀐다면 그와 인접한 칸들만 탐색해주면 되고 수정한 칸들은 이후에는 바뀔 일이 없을 테니 $Q$번에 쿼리동안 총 $N^2$연산을 하므로 시간복잡도가 $O(N^2 + Q)$이 된다. 인접한 칸들 중 바뀔 칸들을 탐색해주는 작업은 bfs로 하였다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
typedef pair<int,int> pii;
const int NMAX = 1000;
const int dr[]  = {0,0,0,-1,1}, dc[] = {0,-1,1,0,0};
int direcNum(char d){
    if(d == 'L') return 1;
    if(d == 'R') return 2;
    if(d == 'U') return 3;
    if(d == 'D') return 4;
    return 0;
}

int N, Q, totalUnusable = 0;
int Greed[NMAX + 10][NMAX + 10]; //0->'?',1234->LRUD
bool canExit[NMAX + 10][NMAX + 10];
stack<pii> Query;

bool ableToExist(int r, int c){
    int g = Greed[r][c];
    bool rtv= false;
    if(!g){
        for(int i=1;i<=4;i++) {
            int nr = r + dr[i], nc = c + dc[i]; 
            if(nr < 1 || nc < 1 || nr > N || nc > N) return true;
            rtv = rtv || canExit[nr][nc];
        }
    } else {
        int nr = r + dr[g], nc = c + dc[g]; 
        if(nr < 1 || nc < 1 || nr > N || nc > N) return true;
        rtv = rtv || canExit[nr][nc];
    }
    return rtv;
}

void dfs(int r, int c){
    if(r < 1 || c < 1 || r > N || c > N) return;
    if(canExit[r][c] || !ableToExist(r,c)) return;
    int g = Greed[r][c];
    canExit[r][c] = true;
    for(int i=1;i<=4;i++) dfs(r+dr[i],c+dc[i]);
    return;
}

void bfs(int r, int c){
    int g = Greed[r][c];
    Greed[r][c] = 0;
    if(canExit[r][c]) return;
    
    for(int i=1;i<=4;i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        if(nr < 1 || nc < 1 || nr > N || nc > N) canExit[r][c] = true;
        else {
            canExit[r][c] = canExit[r][c] || canExit[r+dr[i]][c+dc[i]];
        }
    }
    if(!canExit[r][c]) return;
    
    queue<pair<int,int>> q;
    q.push({r,c});
    while(!q.empty()){
        int R = q.front().first;
        int C = q.front().second;
        q.pop();
        
        totalUnusable --;
        for(int i=1;i<=4;i++){
            int nr = R + dr[i];
            int nc = C + dc[i];
            if(nr < 1 || nc < 1 || nr > N || nc > N) continue;
            if(canExit[nr][nc]) continue;
            int G = Greed[nr][nc];
            if(!G) {
                q.push({nr,nc});
                canExit[nr][nc] = true;
            }
            else {
                if(nr + dr[G] == R && nc + dc[G] == C) {
                    q.push({nr,nc});
                    canExit[nr][nc] = true;
                }
            }
        }
    }
}

void solve(){
    for(int r=1;r<=N;r++)
        for(int c=1;c<=N;c++)
            dfs(r,c);
    
    for(int r=1;r<=N;r++)
        for(int c=1;c<=N;c++)
            if(!canExit[r][c]) totalUnusable++;

    stack<int> ans;
    ans.push(totalUnusable);
    while(Q--){
        int r = Query.top().first;
        int c = Query.top().second;
        Query.pop();
        bfs(r,c);
        ans.push(totalUnusable);
    }
    ans.pop();
    while(!ans.empty()){
        cout<<ans.top()<<"\n";
        ans.pop();
    }
}

int main(){
    fastio;
    cin>>N>>Q;
    for(int i=0;i<Q;i++){
        int r,c; cin>>r>>c;
        char direc; cin>>direc;
        Query.push({r,c});
        Greed[r][c] = direcNum(direc);
    }
    solve();
}

 

 

KOI 2011. 그리드 게임

bfs

 문제를 보자마자 색이 같은 인접한 구역들 각각을 하나의 정점으로 봐야겠다라고 생각했다. 그러면 주어진 문제 상황은 홀수 사이클이 없는 그래프에- 대한 문제로 바뀐다. 또한 정점의 개수는 $M,N \leq 100$ 이므로 칸의 개수가 최대 $10^4$ 개이므로, 체스판 컬러링일 때 $10^4$ 개로 최대이다. 따라서 대충 정점의 개수를 $V$개라고 할 때 $O(V^2)$정도를 최적화하면 가능할 것이라 생각했다. 다시 문제를 살펴보면 주어진 시행은 그래프에서 어떤 정점에 대해 그와 인접한 정점들을 모두 흡수하는 것이라고 생각할 수 있다. 이 시행을 반복하다 결국 한개의 정점만 남개되면 시행이 종료되는 것이다. 그렇게 생각하고 보니 매 시행 당 시행한 정점에 대해 다른 정점들과의 거리가 1씩 줄어듬을 확인할 수 있었다. 따라서 그 정점에서 다른 정점까지의 거리 중 최댓값만큼은 시행해야한다는 것을 알 수 있고, 이 값들 중 최솟값이 정답이 된다. 최악의 경우에 시간복잡도는 $O((M\times N )^2)$이 된다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
typedef pair<int,int> pii;
const int NMAX = 100, INF = 1e8;
const int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};

int M, N, ccNum[NMAX + 10][NMAX + 10], cnt=0, ans = INF;
bool grid[NMAX + 10][NMAX + 10];
vector<int> graph[NMAX * NMAX + 10];

bool isOOB(int x, int y){
    if(x < 0 || x >= N || y < 0 || y >= M) return true;
    return false;
}

int bfs(int v){
    queue<int> q;
    int ret = 0;
    int dp[cnt + 10];fill(dp,dp+cnt+1,INF);
    dp[v] = 0;
    q.push(v);
    while(!q.empty()){
        int x = q.front(); q.pop();
        for(int i=0;i<graph[x].size();i++){
            int nx = graph[x][i];
            if(dp[nx] <= dp[x] + 1) continue;
            dp[nx] = dp[x] + 1;
            ret = max(ret, dp[nx]);
            if(ret >= ans) return INF;
            q.push(nx);
        }
    }
    return ret;
}

void solve(){
    bool isVisited[N][M]; fill(&isVisited[0][0], &isVisited[0][0] + N * M, false);
    priority_queue<pii> pq;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++){
            if(isVisited[i][j]) continue;
            cnt++; ccNum[i][j] = cnt;
            bool flag = grid[i][j];
            queue<pii> q; q.push({i,j});
            isVisited[i][j] = true;
            while(!q.empty()){
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                for(int k=0;k<4;k++){
                    int nx = x+dx[k], ny = y+dy[k];
                    if(isOOB(nx,ny) || isVisited[nx][ny]) continue;
                    if(flag != grid[nx][ny]) continue;
                    isVisited[nx][ny] = true;
                    ccNum[nx][ny] = cnt;
                    q.push({nx,ny});
                }
            }
        }
    fill(&isVisited[0][0], &isVisited[0][0] + N * M, false);
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(isVisited[i][j]) continue;
            set<int> s;
            int std = ccNum[i][j];
            queue<pii> q; q.push({i,j});
            isVisited[i][j] = true;
            while(!q.empty()){
                int x = q.front().first, y = q.front().second;
                q.pop();
                for(int k=0;k<4;k++){
                    int nx = x+dx[k], ny = y+dy[k];
                    if(isOOB(nx,ny)) continue;
                    if(std == ccNum[nx][ny]) {
                        if(isVisited[nx][ny]) continue;
                        isVisited[nx][ny] = true;
                        q.push({nx,ny});
                    } else {
                        auto it = s.find(ccNum[nx][ny]);
                        if(it != s.end()) continue;
                        s.insert(ccNum[nx][ny]);
                    }
                }
            }
            auto it = s.begin();
            while(it != s.end()){
                graph[std].push_back(*it);
                it = next(it);
            }
        }
    }
    for(int i=1;i<=cnt;i++){
        ans = min(ans, bfs(i));
    }
    cout<<ans;
}

int main(){
    fastio;
    cin>>N>>M;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            cin>>grid[i][j];
    solve();
}

 

 

BOJ 14942. 개미

dfs, prefix sum, binary search

 원래는 이 문제가 sparse table을 써서 푸는 문제같은데 처음에 생각한대로 코드를 짜다보니 되게 짧고 간단하고 신박한$($?$)$ 풀이가 나와서 그 풀이대로 써보려고 한다. 

 주어진 트리를 1번 정점을 root node로 하는 트리의 형태로 바꿔보자. 7번 정점 관점에서 보았을 때 7번 정점에 있던 개미가 어디까지 갈 수 있을 지를 알려면 1부터 7을 잇는 최단 경로 상에서 7부터 1까지의 간선 가중치를 기준으로 prefix sum한 배열과 그 개미가 가진 에너지를 비교하면 알 수 있다. 이 경우에서는 40이 30과 50 사이에 존재하기 때문에 30까지만 갈 수 있고 거기에 해당하는 2번 정점이 구하는 정점이 될 것이다. $O(N^2)$이 가능했다면 느긋하게 모든 정점에 대해 경로를 구하고 여기에 맞는 누적합 배열도 구해서 풀렸겠지만 $N \leq 10^5$ 이므로 $O(N\log{}{N})$ 정도의 풀이가 필요하다. 이는 1번 정점에서부터 dfs를 하는 것으로 해결할 수 있다. 이때 가중치와 현재까지의 경로를 담은 vector을 다음 정점에 넘겨주어여한다. 하나 해결해야할 문제는 누적합 배열의 시작점이 그림에서는 7번 정점이지만 1번 정점부터 dfs를 한다면 일반적인 방법으로는 안된다. 그래서 가중치에 -1을곱해서 더해나갈 생각을 했다$($!!$)$. 이런 아이디어 덕분에 일반적이지 않은 풀이로 풀 수 있게 되었다. 시간복잡도는 $O(N\log{}{N})$이다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
const int nmax = 1e5;

bool cmp(ll a, ll b){ return a > b; }

int n;
ll energy[nmax + 10], canReachRoom[nmax + 10];
vector<pll> graph[nmax + 10];
bool isVisited[nmax + 10];

void dfs(int S, vll v1, vll v2){
    ll effEnergy = energy[S] + v1.back();
    int idx = lower_bound(v1.begin(),v1.end(),effEnergy,cmp) - v1.begin();
    canReachRoom[S] = v2[idx];
    
    for(int i=0;i<graph[S].size();i++){
        ll V = graph[S][i].first, w = graph[S][i].second;
        if(isVisited[V]) continue;
        isVisited[V] = true;
        v1.push_back(-1*w+v1.back());
        v2.push_back(V);
        dfs(V,v1,v2);
        v1.pop_back(); v2.pop_back();
    }
}

int main(){
    fastio;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>energy[i];
    for(int i=1;i<n;i++){
        ll a,b,c; cin>>a>>b>>c;
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }
    vll v1 = {0}, v2 = {1};
    isVisited[1] = true;
    dfs(1,v1,v2);
    for(int i=1;i<=n;i++) cout<<canReachRoom[i]<<"\n";
}

 

 KOI 2022. 트리와 쿼리

union-find, dfs

문제를 접근할 발상 자체는 쉬운데 최적화가 좀 어려웠던 문제이다. 일단 주어진 $K \leq N$ 개의 정점에 대해 분리집합을 찾고 그 분리집합들에 속한 원소들의 개수를 모두 구해주면 된다. 이때 어떤 분리집합 $D$에 $V$개의 정점이 속한다고 하면 이 집합의 연결 강도는 $V \choose 2$이므로 구하는 정답은 $\sum_{D\in S}^{}{V(D) \choose 2}$이 된다. 분리집합들을 찾는 것은 집합 $S$에 속한 주어진 $K$개의 정점에 대해 그와 인접한 정점들 중 $S$에 속하는 정점이 있다면 그 정점과 union을 해주는 식으로 하면 $O(NK)$만에 구할 수 있다. 그리고 이는 명백히 시간초과이다. 여기서 최적화를 해야하는데 K개의 정점들에 대해 이터레이션하는 횟수를 줄여주면 된다. 그러기 위해 간선들의 개수를 줄일 생각을 할 수 았고, 트리이므로 부모노드와 자식 노드 중 자식노드에만 간선을 저장해주어도 상관없다. 

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
const int NMAX = 3e5;
typedef long long ll;

vector<int> tmpGraph[NMAX + 10], graph[NMAX + 10], vertices;
int N,K,parent[NMAX + 10],rk[NMAX + 10];
ll parentNum[NMAX + 10], ans = 0;
bool inQuery[NMAX + 10];

int getParent(int x){
    if(parent[x] == x) return x;
    return parent[x] = getParent(parent[x]);
}

void unionParent(int x, int y){
    x = getParent(x); y = getParent(y);
    if(x == y) return;
    if(rk[x] > rk[y]) parent[y] = x;
    else {
        parent[x] = y;
        if(rk[x] == rk[y]) rk[y] ++;
    }
}

void init(){
    for(int i=0;i<K;i++) {
        int v = vertices[i];
        parent[v] = v; 
        rk[v] = 0;
        inQuery[v] = false;
    }
    vertices.clear();
    ans = 0;
}

void dfs(int cur, int bef){
    for(int i=0;i<tmpGraph[cur].size();i++){
        int v = tmpGraph[cur][i];
        if(v == bef) continue;
        graph[v].push_back(cur);
        dfs(v,cur);
    }
}

void solve(){
    for(int i=0;i<K;i++){
        int v = vertices[i];
        for(int j=0;j<graph[v].size();j++){
            int u = graph[v][j];
            if(!inQuery[u]) continue;
            unionParent(u,v);
        }
    }
    
    for(int i=0;i<K;i++) parentNum[getParent(vertices[i])] ++;
    
    for(int i=0;i<K;i++){
        int p = getParent(vertices[i]);
        if(parentNum[p] == 0) continue;
        ans += (parentNum[p]*(parentNum[p]-1))/2;
        parentNum[p] = 0;
    }
}

int main(){
    fastio;
    cin>>N;
    for(int i=0;i<N-1;i++){
        int v,u; cin>>v>>u;
        tmpGraph[v].push_back(u);
        tmpGraph[u].push_back(v);
    }
    for(int i=1;i<=N;i++) parent[i] = i;
    dfs(1,0);
    
    int Q; cin>>Q;
    while(Q--){
        cin>>K;
        for(int i=0;i<K;i++){
            int v; cin>>v;
            vertices.push_back(v);
            inQuery[v] = true;
        }
        solve();
        cout<<ans<<"\n";
        init();
    }
}