BOJ1486 등산

그래프의 간선 가중치에 대해 조금만 생각해보면 핵심적인 아이디어를 떠올릴 수 있습니다.

간선의 존재여부 및 그 가중치를 인접행렬이나 인접리스트로 저장하는 대신, 인접한 두 위치와 그 높이를 갖고 간선 존재여부 및 가중치를 O(1)에 계산할 수 있습니다.

이 격자 그래프에서 노드의 개수는 최대 625개이고, 간선의 수도 이에 선형비례하므로 다익스트라 알고리즘을 사용해 준다면 시작점에서 모든 노드로 가는 최단시간을 파악할 수 있습니다.

한 가지 문제점은 우리가 고려할 경로는 가는 경로뿐만 아니라 오는 경로도 있다는 것이지만, 이는 간선 가중치를 부여할 때 간선의 시작점과 끝점을 뒤집어 가중치를 판단함으로써 해결 가능합니다.

이에 따라 시작점에서 모든 점까지의, 모든 점에서 시작점까지의 최단경로를 구할 수 있고 이것의 합이 제한 시간보다 작은 노드 중 높이가 최대인 노드를 찾으면 됩니다.

이것을 코드로 옮기면 다음과 같이 작성할 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using dat=pair<int,pii>;

const int inf=0x3f3f3f3f;
int n,m,t,d;
string arr[25];
int d1[25][25],d2[25][25];

const int dx[]={0,0,-1,1};
const int dy[]={-1,1,0,0};

int cti(char x){
	return (x|32)-'a'+(x&32)/16*13;
}

int vpos(int x,int y){
	return x>=0&&x<n&&y>=0&&y<m;
}

int dist(int a,int b,int x,int y){
	if(abs(cti(arr[a][b])-cti(arr[x][y]))>t)return inf;
	int q=cti(arr[a][b]);//start
	int w=cti(arr[x][y]);//end
	if(q>=w)return 1;
	return (w-q)*(w-q);
}

int main(void){
	ios::sync_with_stdio(0);cin.tie(0);
	memset(d1,'?',sizeof(d1));
	memset(d2,'?',sizeof(d2));
	cin>>n>>m>>t>>d;
	for(int i=0;i<n;i++)cin>>arr[i];
	d1[0][0]=d2[0][0]=0;
	{
		priority_queue<dat> q;
		q.push(dat(-0,pii(0,0)));
		while(!q.empty()){
			int dst,a,b;
			dst=-q.top().first;
			tie(a,b)=q.top().second;
			q.pop();
			dst=-dst;
			if(dst>d1[a][b])continue;
			for(int i=0;i<4;i++){
				int nx=a+dx[i];
				int ny=b+dy[i];
				if(!vpos(nx,ny))continue;
				int dd=dist(a,b,nx,ny);
				if(d1[nx][ny]>d1[a][b]+dd){
					d1[nx][ny]=d1[a][b]+dd;
					q.push(dat(-d1[nx][ny],pii(nx,ny)));
				}
			}
		}
	}
	{
		priority_queue<dat> q;
		q.push(dat(-0,pii(0,0)));
		while(!q.empty()){
			int dst,a,b;
			dst=-q.top().first;
			tie(a,b)=q.top().second;
			q.pop();
			if(dst>d2[a][b])continue;
			for(int i=0;i<4;i++){
				int nx=a+dx[i];
				int ny=b+dy[i];
				if(!vpos(nx,ny))continue;
				int dd=dist(nx,ny,a,b);
				if(d2[nx][ny]>d2[a][b]+dd){
					d2[nx][ny]=d2[a][b]+dd;
					q.push(dat(-d2[nx][ny],pii(nx,ny)));
				}
			}
		}
	}
	int mx=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(d1[i][j]+d2[i][j]>d)continue;
			mx=max(mx,cti(arr[i][j]));
		}
	}
	cout<<mx;
}
yubin.choi's profile image

최유빈(yubin.choi)

2020-08-21 00:00

Read more posts by this author