[알고리즘] 백준 1486 등산

📖문제

1468 등산

💡구상

다른 지점으로 이동할 때, 걸리는 시간이 다르다?
노드에서 노드로 가는게 가중치가 다르다면 BFS는 사용할 수 없다.

BFS는 가중치가 같은 그래프에서 사용할 수 있다.

또 산에 갔다가 다시 호텔로 돌아와야 하기 때문에, 단방향인 다익스트라 알고리즘은 사용할 수 없다.

그리고 시간이 단위인데, 음의 가중치가 없으므로 플로이드 워셜 알고리즘을 이용해서 구해보자.

🔍코드

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[26][26],b[3000][3000];
const int INF = 987654321;
int n,m,t,d,ret;
vector<int> v;
string s;
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};

int main() {
	cin>>n>>m>>t>>d;
	for(int i=0; i<n; i++){
		cin>>s;
		for(int j=0; j<m; j++){
			if(s[j]>='A'&&s[j]<='Z') a[i][j]=s[j]-'A';
			if(s[j]>='a'&&s[j]<='z') a[i][j]=s[j]-'a'+26;
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			v.push_back(i*100 +j);
		}
	}
	
	ret = a[0][0];
	fill(&b[0][0],&b[0][0]+3000*3000, INF);
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			for(int d=0; d<4; d++){
				int ny = i+dy[d];
				int nx = j+dx[d];
				
				if(ny<0 || ny>=n || nx<0 || nx>=m) continue;
				int height_diff = abs(a[i][j] - a[ny][nx]);
				// 높이차가 t이하면 
				if(height_diff <= t){
					if(a[ny][nx]>a[i][j]){
						b[i*100 + j][ny*100 + nx] = height_diff * height_diff;
					}else b[i*100 + j][ny*100 + nx] = 1;
				}
			}
		}
	}
	
	// 정점 갱신 
	for(int k : v){
		for(int i : v){
			for(int j : v){
				b[i][j] = min(b[i][j], b[i][k]+b[k][j]);
			}
		}
	}
	
	// 조건에 따른 최댓값 반환 
	for(int j:v){
		if(d >= b[0][j] + b[j][0]){
			ret = max(ret, a[j/100][j%100]);
		}
	}
	cout<<ret;
	return 0;
}

플로이드 워셜 2차원??

현재 2차원 배열에서 탐색해야 하는데, 플로이드 워셜은 1차원 배열에서 탐색이 가능하다.

그럼 2차원 배열을 1차원 배열로 바꿔보자.
현재 N,M이 최대 25이므로 [i][j]를 [i*100+j]로 변환할 수 있다.

for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			v.push_back(i*100 +j);
		}
	}

b배열

b배열은 정점간 소모값(시간)을 나타낸다.
b[0][n]은 b[0]에서 b[n]으로 가는데 걸리는 시간이다.

정점 갱신(플로이드 워셜)

for(int k : v){
		for(int i : v){
			for(int j : v){
				b[i][j] = min(b[i][j], b[i][k]+b[k][j]);
			}
		}
	}

모든 쌍을 확인하면서 최솟값을 갱신해준다.

원래 값 반환

2차원 배열을 1차원 배열로 변환하였으니, 다시 변환할때는 아래와 같이 접근할 수 있다.

ret = max(ret, a[j/100][j%100]);

🔥배운 점

상황에 맞는 알고리즘을 사용하기 위해 해당 알고리즘을 사용할 수 없는 조건을 잘 명시해두자!