[백준] 등산 (1486번)

문제

세준이는 등산광이다. 세준이는 높은 곳에서 도시를 내려다 보는 것을 좋아한다. 하지만, 겁이 많은 세준이는 어두워지기 전에 호텔로 내려오려고 한다.

세준이가 가려고하는 산의 지도가 입력으로 주어진다. 산의 지도를 M이라고 했을 때, M[i][j]는 (i,j)의 높이가 M[i][j]라는 것을 의미한다. 그 값이 'A'-'Z'일 때는 0-25를 뜻하는 것이고, 'a'-'z'일 때는, 26-51을 뜻한다.

세준이의 호텔은 (0,0)에 있다. 그리고, 세준이는 지금 위치에서 바로 인접한 정수 좌표 중 높이의 차이가 T보다 크지 않은 곳으로만 다닐 수 있다.

만약 세준이가 현재 위치에서 높이가 낮은 곳이나 같은 곳으로 이동한다면 시간은 1초가 걸린다. 하지만 높은 곳으로 이동한다면 두 위치의 높이의 차이의 제곱만큼 시간이 걸린다. 예를 들어 높이가 5에서 높이가 9인 곳으로 간다면, 시간은 (5-9)2=16초가 걸린다. 하지만, 높이가 9인 곳에서 5인 곳으로 간다면 시간은 1초가 걸린다.

산의 지도와, T, 그리고 어두워지는 시간 D가 주어졌을 때, 세준이가 D보다 크지 않은 시간 동안 올라갈 수 있는 최대 높이를 구하는 프로그램을 작성하시오.(세준이는 호텔에서 출발해서 호텔로 돌아와야 한다.)

입력

첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 세준이가 갈 수 있는 가장 높은 곳의 높이를 출력한다.

예제 입력 1 복사

6 6 6 36 AABCDE GJIHGF MKLMNO STSRQP YUVWXY edcbaZ

예제 출력 1 복사

30

---

갈 수 있는 산의 최대 높이를 구하는 문제이다. 

단 등산한 후 하산까지 마쳐야 한다. 이걸 제대로 안 읽어서 틀렸었다.

산의 높이차 T와, 최대 시간 D를 고려하면서 산을 방문해주면 된다.

 

다익스트라나 플로이드 와샬 알고리즘을 통해 해결할 수도 있지만, bfs를 통해 해결했다.

우선 시작점 (1,1)에서 각 지점으로 등산하는 함수 bfs()를 돌린 후,

(1,1)로 하산하는 함수 bfs2()를 돌렸다.

 

bfs()는 문제에서 요구하는 그대로 구현했지만, bfs2()가 약간 헷갈릴 수 있다.

원래는 모든 지점에서 (1,1)로 가는 거리를 구하려면 bfs를 좌표 수만큼 여러번 돌려야 할 것 같아서,

(1,1)로 도착하는 거리를 구한다고 가정하고, 시간 계산을 거꾸로 했다.

예를들어 (1,2)에서 (1,1)로 하산한다고 할 때, 높이가 6과 3이라면 시간은 1이 걸릴 것이다. 이 시간을 (1,2)지점에 기록하는 것이다.

그렇다보니 다음 지점이 오르막일 때엔 시간 + 1을 하고, 내리막일 때 높이차만큼 제곱을 해서 더하는 방식으로 해야한다. 

 

혹시나 이해가 잘 안될까봐 아래 예시 결과를 올렸다.

visit가 등산 시간 배열이고 back이 하산 시간 배열이다. 참고하길 바란다.

 

이렇게 등산과 하산 시간을 모두 구한 후에 최종적인 계산만 하면 된다.

두 시간의 합이 D를 넘지 않을 때 해당 위치의 최대 높이를 반복문을 통해서 구하면 된다.

등산이나 하산이 불가능한 지역은 예외처리를 해야한다. 까먹지 말자.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EB%93%B1%EC%82%B0%20(1486%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int N, M, T, D;
int res;
int p[26][26]; // 지도 정보
int visit[26][26]; // 등산 시간
int back[26][26]; // 하산 시간
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };

void bfs()
{
	memset(visit, -1, sizeof(visit));
	queue<pair<int, int>> q;
	q.push({ 1,1 });
	visit[1][1] = 0;

	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<1 || ny<1 || nx>N || ny>M) continue;
			if (abs(p[nx][ny] - p[x][y]) > T) continue; //높이차가 T보다 크면 불가능
			if (p[nx][ny] <= p[x][y]) {
				if (visit[x][y] + 1 > D) continue; // D시간 초과시 방문 불가능
				if (visit[nx][ny] == -1 || visit[nx][ny] > visit[x][y] + 1) {
					visit[nx][ny] = visit[x][y] + 1;
					q.push({ nx,ny });
				}
			}
			else {
				int nextTime = (p[nx][ny] - p[x][y]) * (p[nx][ny] - p[x][y]);
				if (visit[x][y] + nextTime > D) continue; //D시간 초과시 방문 불가능
				if (visit[nx][ny] == -1 || visit[nx][ny] > visit[x][y] + nextTime) {
					visit[nx][ny] = visit[x][y] + nextTime;
					q.push({ nx,ny });
				}
			}
		}
	}
}

void bfs2()
{
	memset(back, -1, sizeof(back));
	queue<pair<int, int>> q;
	q.push({ 1,1 });
	back[1][1] = 0;

	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<1 || ny<1 || nx>N || ny>M) continue;
			if (abs(p[nx][ny] - p[x][y]) > T) continue; //높이차가 T보다 크면 불가능
			if (p[x][y] > p[nx][ny]) {
				int nextTime = (p[x][y] - p[nx][ny]) * (p[x][y] - p[nx][ny]);
				if (back[x][y] + nextTime > D) continue; // D시간 초과시 방문 불가능
				if (back[nx][ny] == -1 || back[nx][ny] > back[x][y] + nextTime) {
					back[nx][ny] = back[x][y] + nextTime;
					q.push({ nx,ny });
				}
			}
			else {
				if (back[x][y] + 1 > D) continue; // D시간 초과시 방문 불가능
				if (back[nx][ny] == -1 || back[nx][ny] > back[x][y] + 1) {
					back[nx][ny] = back[x][y] + 1;
					q.push({ nx,ny });
				}
			}
		}
	}
}

int main()
{
	cin >> N >> M >> T >> D;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			char a;
			cin >> a;
			if ('A' <= a && a <= 'Z') p[i][j] = (a - 'A');
			else p[i][j] = (a - 'a' + 26);
		}
	}

	bfs(); //호텔 -> 등산
	bfs2(); //산->호텔

	res = p[1][1];
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (visit[i][j] == -1 || back[i][j] == -1) continue;
			if (visit[i][j] + back[i][j] <= D) {
				res = max(res, p[i][j]);
			}
		}
	}

	cout << res;
}