[G2] 백준 1486번 등산 C++ 다익스트라, 정렬

리뷰

 

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

이 문제는 지문을 잘 읽어야 할 것 같다. 예제 일부가 맞지 않아 고심을 좀 한 문제

 

 

전역 변수

• n, m : 맵의 세로/가로 길이를 저장할 변수
• t : 이동 가능한 높이의 최대값을 저장할 변수
• d : 시간 제한을 저장할 변수
• lst : 맵 정보를 입력 받을 2차원 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 산을 올라갈 때 사용할 위치와 시간을 정의할 구조체, 시간을 기준으로 오름차순 정렬한다.
• bPos : 산에서 내려올 때 사용할 높이와 위치, 시간을 정의할 구조체, 높이를 기준으로 내림차순 정렬한다.
• dest : 갈 수 있는 산을 저장하기 위한 bPos타입의 벡터

 

함수

1. go

void go() {
	priority_queue<Pos> pq;
	pq.push({ 0, 0, 0 });
	vector<vector<int>> dist(n, vector<int>(m, 2e9));
	dist[0][0] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, cv = pos.v;
		if (dist[cx][cy] < cv) continue;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && abs(lst[nx][ny] - lst[cx][cy]) <= t) {
				int nv = 1;
				if (lst[nx][ny] > lst[cx][cy]) nv = pow(lst[nx][ny] - lst[cx][cy], 2);
				if (cv + nv > d) continue;
				if (dist[nx][ny] > cv + nv) {
					dist[nx][ny] = cv + nv;
					pq.push({nx, ny, cv + nv});
				}
			}
		}
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (dist[i][j] != 2e9) dest.push_back({ lst[i][j], i, j, dist[i][j] });
		}
	}
}

 

올라갈 수 있는 산의 최단 경로를 dest벡터에 추가하기 위한 함수

 

2. back

bool back(bPos& bpos) {
	priority_queue<Pos> pq;
	pq.push({bpos.x, bpos.y, bpos.v});
	vector<vector<int>> dist(n, vector<int>(m, 2e9));
	dist[bpos.x][bpos.y] = bpos.v;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, cv = pos.v;
		if (dist[cx][cy] < cv) continue;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && abs(lst[nx][ny] - lst[cx][cy]) <= t) {
				int nv = 1;
				if (lst[nx][ny] > lst[cx][cy]) nv = pow(lst[nx][ny] - lst[cx][cy], 2);
				if (cv + nv > d) continue;
				if (!nx && !ny) return true;
				if (dist[nx][ny] > cv + nv) {
					dist[nx][ny] = cv + nv;
					pq.push({ nx, ny, cv + nv });
				}
			}
		}
	}
	return false;
}

 

산에서 호텔까지 내려올 수 있는지 여부를 체크하기 위한 함수

 

 

문제풀이

1. n, m, t, d값을 입력 받고, n * m크기의 맵 정보를 정수로 파싱하여 배열 lst에 저장해 준다.
2. go함수를 호출하여 호텔에서 오를 수 있는 모든 산 정보를 dest벡터에 저장해 준다.
3. sort함수를 통해 dest벡터를 높이를 기준으로 내림차순 정렬해 준다.
4. 변수 ans의 초기값을 호텔의 높이로 저장해 준다.
5. 내림차순 정렬된 dest를 순회하며 back함수의 리턴값이 true인 경우를 찾는다.
6. 만약 true가 반환되었다면 ans를 현재 산의 높이로 저장 후 break처리해 준다.
7. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 위 아래 이동 시 모두 t범위내로 이동이 가능하므로 이동 가능 여부를 체크할 때 절대값을 체크해 주어야 한다.
2. 높이가 높은 산부터 확인해 주면 호텔로 갈 수 있는 산을 찾았을 때 아래 높이의 산은 확인할 필요가 없다.

 

정답 코드

#include<iostream>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;

int n, m, t, d;
int lst[25][25];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos {
	int x, y, v;
	bool operator<(const Pos& other) const {
		return v > other.v;
	}
};
struct bPos {
	int h, x, y, v;
	bool operator<(const bPos& other) const {
		return h > other.h;
	}
};
vector<bPos> dest;

void go() {
	priority_queue<Pos> pq;
	pq.push({ 0, 0, 0 });
	vector<vector<int>> dist(n, vector<int>(m, 2e9));
	dist[0][0] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, cv = pos.v;
		if (dist[cx][cy] < cv) continue;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && abs(lst[nx][ny] - lst[cx][cy]) <= t) {
				int nv = 1;
				if (lst[nx][ny] > lst[cx][cy]) nv = pow(lst[nx][ny] - lst[cx][cy], 2);
				if (cv + nv > d) continue;
				if (dist[nx][ny] > cv + nv) {
					dist[nx][ny] = cv + nv;
					pq.push({nx, ny, cv + nv});
				}
			}
		}
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (dist[i][j] != 2e9) dest.push_back({ lst[i][j], i, j, dist[i][j] });
		}
	}
}

bool back(bPos& bpos) {
	priority_queue<Pos> pq;
	pq.push({bpos.x, bpos.y, bpos.v});
	vector<vector<int>> dist(n, vector<int>(m, 2e9));
	dist[bpos.x][bpos.y] = bpos.v;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, cv = pos.v;
		if (dist[cx][cy] < cv) continue;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && abs(lst[nx][ny] - lst[cx][cy]) <= t) {
				int nv = 1;
				if (lst[nx][ny] > lst[cx][cy]) nv = pow(lst[nx][ny] - lst[cx][cy], 2);
				if (cv + nv > d) continue;
				if (!nx && !ny) return true;
				if (dist[nx][ny] > cv + nv) {
					dist[nx][ny] = cv + nv;
					pq.push({ nx, ny, cv + nv });
				}
			}
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> t >> d;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			char ch; cin >> ch;
			if ('A' <= ch && ch <= 'Z') lst[i][j] = ch - 'A';
			else lst[i][j] = ch - 'a' + 26;
		}
	}

	go();
	sort(dest.begin(), dest.end());
	int ans = lst[0][0];
	for (bPos& bpos : dest) {
		if (back(bpos)) {
			ans = bpos.h;
			break;
		}
	}
	cout << ans;
}