[백준/C++] 더워! (No. 32360)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 가장 빠르게 집에서 약속장소를 도착하는 시간을 찾는 문제므로 BFS로 풀 수 있다.

 

단지, 일반적인 BFS와 다른 점은 불쾌감 지수가 있어서 불쾌감 지수가 100이상이 되면 더 이상 이동할 수 없는 상태가 된다.

그러므로 불쾌감 지수가 100이 되지 않으면서 약속장소에 도달할 수 있도록 불쾌감을 조절하며 가장 빠르게 약속장소에 도착하는 시간을 찾으면 된다.

 

이제 불쾌감 지수를 고려해 BFS로 문제를 푸는 방법을 생각해보자.

 

현재 위치의 불쾌감 지수를 B, 시간을 T라고 하고, 앞으로 이동할 위치에 방문한 적이 있다면 이전에 방문했을 때의 불쾌감 지수를 nB, nT라고 가정하면

 

이때, T>=nT는 항상 성립한다는 사실을 알 수 있다.

왜냐하면 BFS로 탐색을 하므로 이전에 방문한 적이 있다면, 그때의 시간은 항상 현재 시간 T보다 빠르기 때문이다.

 

이제 경우의 수를 나누어 보면

 

1. 다음에 이동할 위치에 저장된 불쾌감 지수 nB가 B+C보다 작거나 같은 경우

2. 다음에 이동할 위치에 저장된 불쾌감 지수 nB가 B+C보다 큰 경우

 

위 두가지 경우에서 1번 경우는 고려할 필요가 없다.

왜냐하면 nT<=T에 의해 시간도 빠르면서 불쾌감 지수가 같거나 더 낮기 때문이다.

 

그러므로 2번 경우만 고려하면 된다. 이제 이동할 위치의 불쾌감 지수 nB가 B+C보다 크므로 nB를 B+C로 갱신하고, queue에 현재 경우를 넣어 BFS로 탐색을 이어나가면 된다.

 

이때, 주의해야할 점은 불쾌감 지수의 최소값은 0보다 크거나 같다는 점이다.

집에 들어가서 불쾌감 지수가 감소하는 경우 0보다 작아지지 않는다,

 

이를 고려해 문제를 구현하면 쉽게 풀 수 있다.

 

​

[아이디어 정리]

1. 약속장소에 가장 빠르게 도착하는 이동시간을 구하는 문제이므로 BFS로 탐색을 한다.
2. BFS로 탐색을 하므로 특정 위치에 방문한 경우 다음에 같은 위치에 오는 경우는 항상 이동시간이 더 늦거나 같다.
3. 2번 조건을 고려하면 특정위치에 방문할 경우 불쾌감 지수가 이전에 방문했을 경우보다 낮은지를 이용해 탐색을 이어나갈지 말지 정할 수 있다.
4. BFS로 탐색을 이어나가다 약속장소에 도착했을 때, 불쾌감 지수가 100보다 작다면 가장 빠르게 도착한 경우이므로 그때의 이동시간을 출력한다.

 

 

 

Code

 

 

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


int dy[5] = { 0,0,1,-1,0 };
int dx[5] = { 1,-1,0,0,0 };
struct info{
	int x;
	int y;
	int fi; //불쾌
	int se; //시간
};
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N,M, K, C;
	cin >> N>>M>>K>>C;
	vector<string> mv(N);
	int x, y;
	for (int i = 0; i < N; i++) {
		cin >> mv[i];
		for (int j = 0; j < M; j++) {
			if (mv[i][j] == 'S') {
				y = i, x = j;
			}
		}
	}
	// 불쾌, 시간
	vector<vector<pair<int, int>>> visited(N, vector<pair<int, int>>(M, { 100, 2987654321 }));
	info np, tmpP;
	np.y = y, np.x = x, np.fi = 0, np.se = 0;
	queue<info> q;
	q.push(np);
	visited[y][x] = { 0,0 };
	int ny, nx;
	while (!q.empty()) {
		np = q.front();
		q.pop();
		for (int i = 0; i < 5; i++) {
			ny = np.y + dy[i];
			nx = np.x + dx[i];
			if (ny >= 0 && ny < N && nx >= 0 && nx < M && mv[ny][nx] != '#') {
				pair<int, int> nTmp = visited[ny][nx];
				if (mv[ny][nx] == '.')
				{
					int nowB = np.fi + C;
					if (nowB<100)
					{
						if (nowB < nTmp.first) {
							visited[ny][nx].first = nowB;
							visited[ny][nx].second = np.se+1;
							tmpP.y = ny, tmpP.x = nx, tmpP.fi = nowB, tmpP.se = np.se + 1;
							q.push(tmpP);
						}
					}
				}
				else if (mv[ny][nx] == 'H')
				{
					int nowB = max(0, np.fi - K);
					if (nowB < nTmp.first) {
						visited[ny][nx].first = nowB;
						visited[ny][nx].second = np.se + 1;

						tmpP.y = ny, tmpP.x = nx, tmpP.fi = nowB, tmpP.se = np.se + 1;
						q.push(tmpP);
					}
				}
				else if (mv[ny][nx] == 'E') {
					// 끝
					int nowB = np.fi + C;
					if (nowB < 100)
					{
						cout << np.se + 1;
						return 0;
					}
				}
			}
		}
	}
	cout<< -1;
	
	return 0;
}

---

 

처음에 이 문제를 풀었을 때, 분명 맞는데 계속 틀려서 이유를 몰랐다...

다시 풀어야되나 생각하던 중 잘 보니 불쾌지수의 초기값을 0이 아닌 시작점의 좌표 x값으로 초기화 하고 있었다;;

문제를 오랜만에 풀었더니 오타가 자주 나는 것 같은데 다시 알고리즘 공부를 시작하며 오타를 좀 줄여보자...

 

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