백준 17733 - Water Bottle

문제링크 : https://www.acmicpc.net/problem/17733

문제에서 원하는 게
start - end 도시 까지 갈 때 들고가야할 물병사이즈의 최소값이다
start - end 까지 바로 가는게 아니라
인접한 특정도시를 거쳐갈 수 있으면 그것을 고려해 보는게 좋아보인다

일단 주어진 도시들에 번호를 매긴 후
탐색을 통해서 가장 인접한 각각의 도시쌍들끼리 그래프를 만들어준다

구체적으로는
도시를 시작점으로하는 bfs를 통해서 각도시마다 영역을 만들어주고
그 영역들끼리 인접한 곳들(이어지는 곳)을 다시 연결시켜서
그래프(temp배열)를 만들어줬다

이 그래프로 최소스패닝트리(graph배열)를 만들어주었다
인접한 두 노드를 잇는 간선의 최소값만 필요로하니깐..

암튼 그걸이용해서 쿼리문을 처리하면 된다.

start 와 end 사이의 경로를 탐색할 때는 희소배열(dist)에 조상들의 간선 중 max값에 해당하는 값을 저장해둬서 처리해줬다

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
using namespace std;

const int MAX_LEVEL = 20;
const int INF = 1e9;
int H,W,P,Q;
vector<int> v[2010];
int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};
pair<int, int> graph[2010][2010];
int p[200010];
// node ,  dist
vector<pair<int,int>> tree[200010];
int level[200010];int parent[200010][MAX_LEVEL];
int dist[200010][MAX_LEVEL];
int find(int x){
    if(x==p[x]) return x;
    return p[x]=find(p[x]);
}
void bfs(){
    queue<pair<int,int>> q;
    for(int i=0;i<H;i++){
        for(int t=0;t<W;t++){
            if(v[i][t]<0){
                graph[i][t]={-1,-1};
            }else{
                graph[i][t]={0,v[i][t]};
                q.push({t,i});
            }
        }
    }
	while(!q.empty()){
        int x = q.front().first; int y = q.front().second;
        q.pop();
		for(int i=0;i<4;i++){
            int nx=x+dx[i];int ny=y+dy[i];
			if(nx<0||nx>=W||ny<0||ny>=H) continue;
			if(graph[ny][nx].first!=-1||v[ny][nx]==-2) continue;
            graph[ny][nx]={graph[y][x].first+1,graph[y][x].second};
			q.push({nx,ny});
		}
	}
}
void mst(){
	vector<pair<int,pair<int,int>>> temp;
    set<pair<int,int>> s;
	for(int i=0;i<H;i++){
		for(int t=0;t<W;t++){
			if(v[i][t]==-2) continue;
            // 다른영역이라면
			if(i<H-1&&v[i+1][t]!=-2&&graph[i][t].second!=graph[i+1][t].second)
                temp.push_back({graph[i][t].first + graph[i+1][t].first,
                {graph[i][t].second,graph[i+1][t].second}});
			if(t<W-1&&v[i][t+1]!=-2&&graph[i][t].second!=graph[i][t+1].second)
                temp.push_back({graph[i][t].first + graph[i][t+1].first,
                {graph[i][t].second,graph[i][t+1].second}});
		}
	}
	sort(temp.begin(), temp.end());

	for(int i=1;i<=P;i++) p[i]=i;

	for(int i=0;i<temp.size();i++){
		int x=temp[i].second.first, y=temp[i].second.second, d=temp[i].first;
        int a = find(x);int b = find(y);
        if(a==b) continue;
        if(a>b){
            p[a]=b;
        }else{
            p[b]=a;
        }
        tree[x].push_back({y,d});
        tree[y].push_back({x,d});
	}
    // 벽에 막혔을 때 처리
	for(int i=1;i<=P;i++){
        int a = find(i); int b = find(i-1);
        if(a==b) continue;
        if(a>b){
            p[a]=b;
        }else{
            p[b]=a;
        }
        tree[i].push_back({i-1,INF});
        tree[i-1].push_back({i,INF});
    }
}
void init_lca(int node,int pnode,int lv,int d){
    level[node]=lv;
    parent[node][0]=pnode;dist[node][0]=d;
    for(int i=1;i<MAX_LEVEL;i++){
        parent[node][i]=parent[parent[node][i-1]][i-1];
        dist[node][i]=max(dist[node][i-1],dist[parent[node][i-1]][i-1]);
    }
    for(auto next : tree[node]){
        int child = next.first;int d = next.second;
        if(child == pnode) continue;
        init_lca(child,node,lv+1,d);
    }
}
int query(int a,int b){
    if(a==1 || b==1){
        return max(dist[a][MAX_LEVEL-1],dist[b][MAX_LEVEL-1]);
    }
    if(level[a]<level[b]) swap(a,b);
    int ret = 0;
    if(level[a]!=level[b]){
        for(int i=MAX_LEVEL-1;i>=0;i--){
            if(level[parent[a][i]]>=level[b]){
                ret = max(ret,dist[a][i]);
                a = parent[a][i];
            }
        }
    }
    if(a==b) return ret;
    for(int i=MAX_LEVEL-1;i>=0;i--){
        if(parent[a][i]!=parent[b][i]){
            ret = max({ret,dist[a][i],dist[b][i]});
            a = parent[a][i];b = parent[b][i];
        }
    }
    ret = max({ret,dist[a][0],dist[b][0]});
    return ret;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>H>>W>>P>>Q;
	for(int i=0;i<H;i++){
		string a;cin>>a;
		for(int t=0;t<a.length();t++){
            if(a[t]=='.') v[i].push_back(-1);
            else v[i].push_back(-2);
		}
	}
	for(int i=1;i<=P;i++){
		int a,b;
		cin>>a>>b;
		v[a-1][b-1]=i;
	}
	bfs();
	mst();
    init_lca(1,0,1,0);
	for(int i=0;i<Q;i++){
		int s,e;
		cin>>s>>e;
		int ret=query(s,e);
        if(ret==INF){
            cout<<"-1"<<"\n";
        }else{
            cout<<ret<<"\n";
        }
	}
}