[백준] 죽음의 비

유승선 ·2022년 10월 14일
0

백준

목록 보기
57/64

꽤 빈번히 나오는 완전탐색류 라고 생각했지만 생각보다 조건이 까다로운 부분도 있어서 애를 좀 먹었다. 가장 밑에 안전지대 까지 가는 최소 경로를 구해야 하는 문제였지만 U 로표시되어있는 우산의 내구도를 신경 써주면서 가야했었다.

이 문제는 예전에 SK 코테에서 풀었던 캠프 문제와 유사하다고 생각했는데 뭔가 맞는거 같다. 원래는 visited 배열을 다차원으로 늘려서 BFS를 할 생각이였는데 너무 복잡해졌다. visited[a][b][우산][내구도] 이런식으로 진행 하게되면 아무리 BFS여도 너무나도 많은 상태를 넣을거 같았기에, 체력과 내구도를 포함해서 Dijkstra 같은 구현을 했다. 체력 + 내구도가 높으면 높을수록 더 멀리 나갈거라는 가정을 전제하에 풀게되었다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N, H, D; //변의 길이, 체력, 내구도 
char matrix[501][501]; 
int visited[501][501]; 
pair<int,int> start;
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}}; 

struct Person{
    pair<int,int> loc; 
    int health; 
    bool umbrella; 
    int power; 
    int distance; 
};

void Input(){
    cin >> N >> H >> D; 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> matrix[i][j]; 
            if(matrix[i][j] == 'S') start = {i,j}; 
            //if(matrix[i][j] == 'E') ending = {i,j}; 
        }
    }
}


void Solution(){
    memset(visited,-1,sizeof(visited)); 
    queue<Person> q; 
    q.push({start,H,false,0,0}); 
    visited[start.first][start.second] = INT_MAX; 
    int answer = -1; 
    while(!q.empty()){
        int size = q.size(); 
        for(int i = 0; i < size; i++){
            Person first = q.front();
            q.pop(); 

            // if(matrix[x][y] == 'E'){
            //     cout << distance;
            //     return; 
            // }

            // if(matrix[x][y] == 'U'){
            //     health += 1; 
            //     umbrella = true; 
            //     power = D; 
            // }
            
            // if(power <= 0) umbrella = false; 
            // if(health <= 0) continue; 

            for(pair<int,int>& p : dir){
                int x = first.loc.first, y = first.loc.second, health = first.health, power = first.power; 
                int distance = first.distance; 
                bool umbrella = first.umbrella; 

                int nX = x + p.first; 
                int nY = y + p.second; 

                if(nX < 0 || nX >= N || nY < 0 || nY >= N) continue; 

                if(matrix[nX][nY] == 'E'){
                    cout << distance + 1; 
                    return; 
                }

                if(matrix[nX][nY] == 'U'){
                    power = D; 
                }

                if(power != 0){
                    power--; 
                }
                else{
                    health--; 
                }

                //cout << x << ' ' << y << ' ' << health << ' ' << power << endl; 
                if(health == 0) continue; 

                if(visited[nX][nY] < (health + power)){
                    visited[nX][nY] = health + power; 
                    q.push({{nX,nY},health,umbrella,power,distance+1});
                    //if(umbrella) q.push({{nX,nY},health,umbrella,power-1,distance+1}); 
                    //if(!umbrella) q.push({{nX,nY},health-1,umbrella,power,distance+1}); 
                }
            }


        }
    }
    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}
profile
성장하는 사람

0개의 댓글