문제
가로, 세로 길이가
인 정사각형 격자가 있다. 해당 격자에는 두 곳을 제외한 모든 곳에 체력을 1씩 감소시키는 죽음의 비가 내리고 있다. 죽음의 비가 안내리는 곳은 현재 있는 위치와 안전지대라는 곳이다. 현재 있는 위치에도 곧 비가 내릴 예정이라 빨리 이 죽음의 비를 뚫고 안전지대로 이동해야한다.
다행히도 격자에는 죽음의 비를 잠시 막아주는 우산이
개 존재한다. 우산에는 내구도
라는 개념이 존재한다. 우산에 비를 맞으면 내구도가 1씩 감소하고, 내구도가 0이 되는 순간 우산은 사라진다. 문제에서 주어지는 우산의 내구도는 모두
로 동일하다.
격자에서 이동을 할 때 다음과 같이 순서로 진행된다.
- 상하좌우로 이동한다. 만약 이동할 곳이 격자 밖이라면 이동할 수 없다.
- 이동한 곳이 안전지대라면 반복을 종료한다.
- 이동한 곳에 우산이 있다면 우산을 든다. 만약, 이동할 때부터 우산을 가지고 있다면 가지고 있는 우산을 버리고 새로운 우산으로 바꾼다.
버린 우산은 더 이상 사용할 수 없다. - 죽음의 비를 맞았을 때, 우산을 가지고 있다면 우산의 내구도가 1이 감소하고 만약 우산을 가지고 있지 않는다면 체력이 1 감소한다.
- 만약 우산의 내구도가 0이 되면 들고 있는 우산이 사라진다.
- 만약 체력이 0이 되면 죽는다...
- 아직 체력이 남았다면 안전지대까지 위 과정을 반복한다.
현재 있는 위치에서 안전지대로 얼마나 빠르게 이동할 수 있는지 구해주자.
입력
첫 번째 줄에 정사각형 격자의 한변의 길이인
와 현재 체력
, 우산의 내구도
가 공백으로 구분되어 주어진다.
다음
개의 줄에는 정사각형 격자의 정보가
개의 문자로 붙어서 주어진다. 이때 주어지는 문자는 우산은 "U", 현재 있는 위치 "S", 안전지대 "E", 빈 칸 "."만 존재한다. 현재 있는 위치 "S"와 안전지대 "E"는 반드시 1개 존재한다.
출력
안전지대로 이동할 때 최소 이동 횟수를 출력한다. 만약 안전지대로 이동하지 못하는 경우에는 -1을 출력한다.
풀이
BFS로 풀 수 있고, 백트래킹으로 풀 수 있다.
BFS로 풀게 된다면 다른 최단거리 구하는 문제와 비슷하게 풀 수 있다.
하지만 주의해야 할 점은 visited 배열이 true, false로 나누어지지 않고 int 형으로 이루어진다는 것이다.
만약 출발점에서 목적지와 우산의 위치가 반대이고, h로 한번에 목적지 갈 수 없어 우산을 들고 목적지에 가야하는 경우가 생긴다면 이미 방문했던 위치라도 다시 밟고 갈 수 있어야 하기 때문이다.
visited에는 현재 위치에서의 h+d 값을 저장해서 움직일 때마다 그 값이 점점 줄어들며,
현재 h+d값과 BFS로 움직일 수 있는 위치(상,하,좌,우)의 visited 값을 비교해서 visited 값이 더 크다면 그 위치로 갈 수 없도록 한다. 따라서 굳이 아무런 생산성없이 움직이는 경우를 배제한다. 우산을 집어들게 된다면 h+d의 값이 커져서 많은 곳으로 움직일 수 있게된다.
visited와 움직인 횟수를 저장 할dist배열이 필요하다.visited는 int로 구성되어야 한다.
백트래킹으로 풀게 된다면 한칸씩 움직이는 것이 아니라 격자에서 각'S', 'E', 'U'를 노드로 생각하여 DFS를 돌아야한다.
각 노드들 사이의 간선의 가중치는 격자에서의 거리로 저장한다.
당연하지만 한칸씩 DFS를 하는 것이 아닌 유의미한 위치에서만 DFS를 돌아야 시간초과가 발생하지 않는다. 이 방법을 전혀 생각치 못했다.
그래서 DFS를 돌기위한 준비를 잘 해주어야 한다.
단순하게 DFS만 해도 시간초과가 발생하지는 않았지만 한가지 더 최적화를 해줄 수 있다.
현재 노드에서 바로 목적지('E')로 갈 수 있다면 굳이 DFS로 모든 경우를 구하지 않고 바로 E로 가는 경우를 채택하여 불필요한 경우를 배제할 수 있다.
움직일 때마다 h 혹은 d 가 줄어드는 과정, 우산을 들었을 때의 h와 d 값 결정등이 까다롭고 머리아팠다. 주의해서 해결해주면 된다.
- BFS로 푼다면
visited배열을 int 로 구성해서 다양한 경우를 고려할 수 있도록 해야한다.- 백트래킹으로 푼다면
U, E, S를 노드로 하여 DFS 탐색을 해야 한다.
코드
BFS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
struct Pos{
int x;
int y;
};
struct Player{
int h;
int d;
Pos pos;
};
int n, h, d;
int answer = -1;
vector<string> map;
vector<vector<int>> dist;
vector<vector<int>> visited;
vector<Pos> delta { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
queue<Player> q;
bool OOB(Pos p){
return (p.x < 0 || p.x >= n) || (p.y < 0 || p.y >= n);
}
void BFS(Player start){
q.push(start);
while(!q.empty()){
Player player = q.front();
Pos& v = player.pos;
q.pop();
if (map[v.x][v.y] == 'U'){
player.d = d;
}
else if(map[v.x][v.y] == 'E'){
answer = dist[v.x][v.y];
break;
}
// 'S'와 '.'를 굳이 나누어서 처리하지 않았음,
// 따라서 'S'위치여도 비를 맞도록 되어서 BFS 들어오기전에 h를 +1 해주었음.
player.d == 0 ? player.h -= 1 : player.d -= 1;
for(auto del: delta){
int nx = del.x + v.x;
int ny = del.y + v.y;
if( OOB({nx, ny}) ) continue;
if( visited[nx][ny] >= player.h + player.d ) continue;
if( player.h == 0 ) continue;
visited[nx][ny] = player.h + player.d;
dist[nx][ny] = dist[v.x][v.y] + 1;
q.push({ player.h, player.d, {nx, ny} });
}
}
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
Player player;
cin >> n >> h >> d;
map.assign(n, "");
// visited.assign(n, vector<int>(n, 0));
// dist.assign(n, vector<int>(n, 0));
visited = vector(n, vector<int>(n, 0));
dist = vector(n, vector<int>(n, 0));
Pos startPos;
for(int i=0; i<n; i++){
cin >> map[i];
for (int j=0; j<n; j++){
if (map[i][j] == 'S') {
startPos.x = i;
startPos.y = j;
}
}
}
player.h = h+1; // 시작할 때는 비를 맞지 않음, BFS에 항상 현재 위치에(pop 하는 경우에) 비를 맞도록 설정했음 따라서 S부분하게 비를 맞으면 안되는 상황에서 맞는 부분을 하나 빼줌
player.d = 0;
player.pos = startPos;
BFS(player);
cout << answer << endl;
return 0;
}DFS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Pos{
int idx;
int x;
int y;
char name;
int operator-(const Pos& a){
return abs(x - a.x) + abs(y - a.y);
}
};
struct Player{
int h;
int d;
Pos pos;
};
int n, h, d;
int minTotalDist = 250001;
vector<string> board;
vector<Pos> nodes;
vector<bool> visited;
Pos arrivalPos, startPos;
bool checkArrival(Player player){
int dist = player.pos - arrivalPos;
return player.h + player.d >= dist;
}
void DFS(Player player, int totalDist){
if (checkArrival(player)){ // 남은 h와 d로 E까지 갈 수 있다면 굳이 DFS로 가지 않고 바로 간다, 최단거리를 구하는 것이기 때문에
int dist = player.pos - arrivalPos;
minTotalDist = min(minTotalDist, totalDist + dist);
return;
}else if (player.pos.name == 'U'){
player.d = d - 1; // 우산 들자마자 비 한방 맞음
}
Pos& pos = player.pos;
for (int i=0; i < nodes.size(); i++){
Pos nextNode = nodes[i];
int nextIdx = nextNode.idx;
int dist = pos - nextNode;
if ( player.h + player.d < dist ) continue;
if ( visited[nextIdx] ) continue;
int nexth = player.h;
if (player.d < dist) {
// 다음 목적지는 우산 혹은 도착지점이기 때문에 가는 동안은 비를 맞지만 목적지에 도착하면 우산을 들든 비가 안오든 그래서 한방은 안맞음
nexth = player.h - (dist - player.d) + 1;
}
visited[nextIdx] = true;
DFS({nexth, player.d, nextNode}, totalDist + dist);
visited[nextIdx] = false;
}
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
Player player;
cin >> n >> h >> d;
board.assign(n, "");
int cnt = 0;
for(int i=0; i<n; i++){
cin >> board[i];
for (int j=0; j<n; j++){
if (board[i][j] == '.') continue;
else if (board[i][j] == 'S') {
startPos = {cnt, i, j, 'S'};
nodes.push_back(startPos);
}
else if (board[i][j] == 'E') {
arrivalPos = {cnt, i, j, 'E'};
nodes.push_back(arrivalPos);
}
else if (board[i][j] == 'U') {
nodes.push_back({cnt, i, j, 'U'});
}
cnt++;
}
}
visited = vector<bool> (nodes.size(), false);
player.h = h;
player.d = 0;
player.pos = startPos;
visited[startPos.idx] = true;
DFS(player, 0);
if (minTotalDist == 500 * 500 +1) minTotalDist = -1;
cout << minTotalDist << endl;
return 0;
}