Softeer-연습문제-나무 섭지(C++)

문제 링크 :https://softeer.ai/practice/7726 

난이도 : Lv.3

문제 개요 : 

유령을 피해 탈출구로 갈 수 있는지 여부를 출력

틀린 이유 : 벽의 좌표를 따로 vector로 만들어 사용했는데, 이거 때문에 시간초과가 나왔다.

 

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

bool check(const int x, const int y, const int n, const int m){
    if(0 <= x && x < n && 0 <= y && y < m){
        return true;
    }
    else{
        return false;
    }
}

vector<vector<int>> build_gostmap(const vector<vector<int>> gost, const int n, const int m){
    const int INF = 999999999;
    vector<vector<int>> gostmap(n, vector<int>(m, INF));
    queue<vector<int>> q;
    const vector<vector<int>> move = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    // 초기 큐 설정
    for(int i=0; i < gost.size(); i++){
        q.push({gost[i][0], gost[i][1], 0});
    }

    while(!q.empty()){
        int x = q.front()[0];
        int y = q.front()[1];
        int val = q.front()[2];
        q.pop();
        if(val < gostmap[x][y]){
            gostmap[x][y] = val;
            for(int i=0; i<4; i++){
                int tmp_x = x + move[i][0];
                int tmp_y = y + move[i][1];
                if(check(tmp_x, tmp_y, n, m)){
                    q.push({tmp_x, tmp_y, val + 1});
                }
            }
        }
    }
    
    return gostmap;
}

void print_whether_escape(const vector<vector<int>> gostmap, const vector<string> map, const vector<int> namu){
    const int INF = 999999999, n = gostmap.size(), m = gostmap[0].size();
    vector<vector<int>> realmap(n, vector<int>(m, INF));
    queue<vector<int>> q;
    const vector<vector<int>> move = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    // 초기 큐 설정
    q.push({namu[0], namu[1], 0});

    while(!q.empty()){
        int x = q.front()[0];
        int y = q.front()[1];
        int val = q.front()[2];
        q.pop();
        if(val < gostmap[x][y] && val < realmap[x][y]){
            if(map[x][y] == 'D'){
                printf("Yes");
                return;
            }
            realmap[x][y] = val;
            for(int i=0; i<4; i++){
                int tmp_x = x + move[i][0];
                int tmp_y = y + move[i][1];
                if(check(tmp_x, tmp_y, n, m) && map[tmp_x][tmp_y] != '#'){
                    q.push({tmp_x, tmp_y, val + 1});
                }
            }
        }
    }

    printf("No");
}

int main(int argc, char** argv)
{
    int n, m;
    scanf("%d %d", &n, &m);

    vector<string> map(n);
    vector<int> namu(2);
    vector<vector<int>> gost;
    for(int i=0; i<n; i++){
        cin >> map[i];
        for(int j=0; j<m; j++){
            if(map[i][j] == 'N'){
                namu = {i, j};
            }
            else if(map[i][j] == 'G'){
                gost.push_back({i, j});
            }
        }
    }

    print_whether_escape(build_gostmap(gost, n, m), map, namu);

   return 0;
}

 

문제 해결 방법

1. map의 각 칸마다 유령이 도착가능한 시간을 계산하여 gostmap을 만든다. 이 역할을 build_gostmap 함수에서 담당한다.

2. 유령이 map 밖으로 나갔는지 여부를 check 함수에서 확인해준다.

3. map의 각 칸마다 남우가 도착 가능한 시간을 계산하여 realmap을 만든다. 단, 남우는 유령보다 적은 시간 안에 해당 칸에 도착할 수 있어야 한다. gostmap을 사용하여 이를 확인할 수 있다.

4. 남우가 map 밖으로 나갔는지 여부를 check 함수에서 확인해준다. 이와 더불어 벽으로 이동하려고 하는 지도 확인해봐야 한다.

5. 남우가 출구에 도착하면 Yes, 그렇지 않으면 No를 출력한다.