[BOJ/Gold 2] 백준 32360 더워!(C++)

문제 링크

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

 

문제

한여름의 날씨는 더워도 너무 덥다. 민규는 외출은커녕 집에서 에어컨에 의지한 채 살아가고 있지만, 오늘은 약속이 있어 불가피하게 집 밖으로 나와 약속 장소로 가야 한다. 그러나 시원한 집에서 쉬다 보니 어느새 약속 시간에 늦어버리고 말았다. 빨리 집을 나서야 한다!

밖은 N행 M열의 격자로 이루어져 있다. 격자의 각 칸은 집, 약속 장소, 건물, 벽, 길 중 하나로 이루어져 있다. 집과 건물은 실내이고, 길, 벽, 약속 장소는 실외이다.

밖은 너무 더워 실외에 있을 때는 지속적으로 불쾌함 B가 증가한다. 그러나 중간중간 이동 경로에 있는 실내는 매우 시원하여, 실내를 지나가거나 실내에서 쉬는 동안에는 불쾌함이 감소한다.

초기에 민규의 불쾌함은 0이며, 불쾌함이 100이 되면 민규는 견딜 수 없어 쓰러지고 만다.

민규는 집에서 출발하여 다음과 같은 순서로 행동한다. 1번 행동은 이동 여부와 상관없이 1의 시간이 소요되며, 2번과 3번 행동에 드는 시간은 무시할 수 있을 만큼 짧다.

 

1. 격자판 내에서 상하좌우에 있는 벽이 아닌 인접한 칸으로 이동하거나, 이동하지 않고 가만히 있는다.
2. 현재 있는 칸에 따라서 불쾌함이 증가하거나 감소한다.
   • 현재 있는 칸이 실내라면 불쾌함이 max(0, B − K)까지 감소한다.
   • 현재 있는 칸이 실외라면 불쾌함이 min(100, B + C)까지 증가한다.
3. 약속 장소에 도달하거나 불쾌함이 100이 되면 행동을 멈춘다. 그렇지 않다면 1번으로 돌아간다.

민규가 약속 장소에 쓰러지지 않고 최대한 빠르게 도달할 수 있도록, 민규의 이동 경로를 계산하는 프로그램을 작성해 주자. 단, 약속 장소로 이동하여 불쾌함이 100이 되면 민규는 쓰러지며, 약속 장소에 도달하지 못한 것으로 간주한다.

 

입력

첫 번째 줄에 격자의 크기를 나타내는 정수 N, M이 공백으로 구분되어 주어진다.

두 번째 줄에 실내에서 감소하는 불쾌함, 실외에서 증가하는 불쾌함을 나타내는 정수 K, C가 공백으로 구분되어 주어진다.

세 번째 줄부터 N + 2번째 줄까지 거리의 상태를 나타내는 길이 M의 문자열이 주어진다. i + 2번째 줄의 j번째 문자는 i행 j열의 칸을 이루는 대상을 나타낸다. 만약 문자가 S라면 민규의 집 위치, E라면 약속 장소, H라면 건물, #이라면 벽, .(온점)이라면 길을 의미한다. S와 E는 각각 하나씩 주어진다.

 

출력

민규가 약속 장소에 쓰러지지 않고 도달할 수 있는 최소 시간을 출력한다. 만약 그런 방법이 없다면 -1을 출력한다.

 

제한

•  2 ≤ N, M ≤ 100
•  1 ≤ K, C ≤ 100
•  0 ≤ B ≤ 100
•  1 ≤ i ≤ N
•  1 ≤ j ≤ M
•  i, j와 입력으로 주어지는 모든 수는 정수이다.

 

예제 입력 1

3 4
10 25
S...
#.H.
E...

예제 출력 1

8

예제 입력 2

3 4
10 25
S...
#..H
E...

예제 출력 2

-1

 

알고리즘 분류

• 그래프 탐색

 

풀이

3차원 배열로, 어느 좌표를 불쾌함 몇일 때 방문했는지를 기록하면서 상하좌우로 탐색하거나 현재 칸에 머무른다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 101
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, K, C;
int MAP[MAX][MAX];
pair<int, int> Start;
bool Visited[MAX][MAX][MAX];
int MoveY[5] = { 0,-1,0,1,0 };
int MoveX[5] = { 0,0,-1,0,1 };
int Answer;

void input() {
	cin >> N >> M;
	cin >> K >> C;
	for (int i = 0; i < N; i++) {
		string S;
		cin >> S;
		for (int j = 0; j < M; j++) {
			char Now = S[j];
			if (Now == 'S') {
				MAP[i][j] = 1;
				Start = make_pair(i, j);
			}
			else if (Now == 'E') {
				MAP[i][j] = -1;
			}
			else if (Now == 'H') {
				MAP[i][j] = 1;
			}
			else if (Now == '#') {
				MAP[i][j] = -2;
			}
		}
	}
}

int bfs() {
	queue<pair<pair<int, int>, pair<int, int> > > Q;
	Visited[Start.first][Start.second][0] = true;
	Q.push(make_pair(Start, make_pair(0, 0)));

	while (!Q.empty()) {
		int NowY = Q.front().first.first;
		int NowX = Q.front().first.second;
		int NowB = Q.front().second.first;
		int NowC = Q.front().second.second;
		Q.pop();

		if (NowB >= 100) continue;

		if ((MAP[NowY][NowX] == -1) && (NowB < 100)) {
			return NowC;
		}

		for (int i = 0; i < 5; i++) {
			int NextY = NowY + MoveY[i];
			int NextX = NowX + MoveX[i];
			if ((NextY >= 0) && (NextY < N) && (NextX >= 0) && (NextX < M)) {
				if (MAP[NextY][NextX] > 0) {
					int NextB = max(0, NowB - K);
					if (!Visited[NextY][NextX][NextB]) {
						Visited[NextY][NextX][NextB] = true;
						Q.push(make_pair(make_pair(NextY, NextX), make_pair(NextB, NowC + 1)));
					}
				}
				else if (MAP[NextY][NextX] > -2) {
					int NextB = min(100, NowB + C);
					if (!Visited[NextY][NextX][NextB]) {
						Visited[NextY][NextX][NextB] = true;
						Q.push(make_pair(make_pair(NextY, NextX), make_pair(NextB, NowC + 1)));
					}
				}
			}
		}
	};

	return -1;
}

void settings() {
	Answer = bfs();
}

void printAnswer() {
	cout << Answer << "\n";
}

int main() {
    FASTIO

	input();
	settings();
    printAnswer();

    return 0;
}