소프티어

처음에는 일반 bfs를 사용해서 방문 배열에 최소값을 업데이트하며 값을 구하는 방법으로 시도했습니다.

하지만 3번 tc에서 시간초과가 발생하고 나머지 tc는 정답으로 나왔습니다..

그래서 시간초과를 해결하는 방법이 우선순위 큐를 사용하여 산타의 cost가 작은 이동부터 이동하게 해서

선물이나 도착지점에 먼저 도착하는 것을 빠르게 파악하여 리턴하는 방식으로 하면 시간이 줄 것 이라고 판단하여 그렇게 코드를 작성했는데...

tc3번은 여전히 시간초과이고, 오히려 9번 tc가 오답으로 나오더군요..

알골 장인들의 힘을 빌리고 싶습니다..!

// 일반 bfs를 사용한 코드

/**
 * @file 7420.cpp
 * @brief 소프티어 산타의 텔레포트, queue 사용 버전
 * @version 0.1
 * @date 2024-05-13
 * 
 * @copyright Copyright (c) 2024
 * 
 */
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<queue>


using namespace std;


struct Santa{
    int y, x, cost;
};


vector<vector<int> > map(501, vector<int>(501, 0));
vector<vector<pair<int, int> > > telpo(100001);


int moveY[4]={0,1,0,-1}, moveX[4]={1,0,-1,0}, sizeY=0, sizeX=0, gift_cost = 0;
pair<int, int> gift_pos;


void print_telpo(){
    for(int i=0; i<telpo.size(); i++){
        if (telpo[i].size() == 0) continue;
        cout<<i<<": ";
        for(int j=0; j<telpo[i].size(); j++){
            cout<<telpo[i][j].first<<" "<<telpo[i][j].second<<"  ";
        }
        cout<<"\n";
    }
}

Santa make_santa(int y, int x, int cost){
    Santa santa;
    santa.y = y;
    santa.x = x;
    santa.cost = cost;
    return santa;
}


bool check_outside(int y, int x){
    return y < 1 || y > sizeY || x < 1 || x > sizeX;
}


bool find_gift(int sy, int sx){
    vector<vector<int> > visited(501, vector<int>(501, 987654321));
    queue<Santa> q;
    q.push(make_santa(sy, sx, 0));
    visited[sy][sx] = 0;
    
    while(!q.empty()){
        Santa now = q.front(); q.pop();
        for(int d=0; d<4; d++){
            int ny = now.y + moveY[d];
            int nx = now.x + moveX[d];
            if (check_outside(ny, nx) || map[ny][nx] == -1 || visited[ny][nx] <= now.cost) continue;
            
            // 빈칸인 경우, 텔레포트가 가능한 경우 + 선물인 경우
            if (map[ny][nx] == 0 || map[ny][nx] >= 10 || map[ny][nx] == -2){
                // 빈칸인 경우 + 텔레포트가 가능한 경우 + 선물인 경우
                q.push(make_santa(ny, nx, now.cost));
                visited[ny][nx] = now.cost;
                // 텔레포트가 가능한 경우
                if (map[ny][nx] >= 10){
                    for(int i=0; i<telpo[map[ny][nx]].size(); i++){
                        int ty = telpo[map[ny][nx]][i].first;
                        int tx = telpo[map[ny][nx]][i].second;
                        if (visited[ty][tx] <= now.cost + 1) continue;
                        q.push(make_santa(ty, tx, now.cost+1));
                        visited[ty][tx] = now.cost+1;
                    }
                }
            }
        }
    }
    if (visited[gift_pos.first][gift_pos.second] == 987654321)
        return false;
    gift_cost = visited[gift_pos.first][gift_pos.second];
    return true;
}


int go_dest(int sy, int sx, int scost){
    vector<vector<int> > visited(501, vector<int>(501, 987654321));
    queue<Santa> q;
    q.push(make_santa(sy, sx, scost));
    visited[sy][sx] = scost;
    while(!q.empty()){
        Santa now = q.front(); q.pop();
        for(int d=0; d<4; d++){
            int ny = now.y + moveY[d];
            int nx = now.x + moveX[d];
            if (check_outside(ny, nx) || map[ny][nx] == -1 || visited[ny][nx] <= now.cost) continue;
            // 빈칸인 경우, 텔레포트가 가능한 경우 + 선물인 경우
            if (map[ny][nx] == 0 || map[ny][nx] >= 10 || map[ny][nx] == -2){
                // 빈칸인 경우 + 텔레포트가 가능한 경우 + 선물인 경우
                q.push(make_santa(ny, nx, now.cost));
                visited[ny][nx] = now.cost;
                // 텔레포트가 가능한 경우
                if (map[ny][nx] >= 10){
                    for(int i=0; i<telpo[map[ny][nx]].size(); i++){
                        int ty = telpo[map[ny][nx]][i].first;
                        int tx = telpo[map[ny][nx]][i].second;
                        if (visited[ty][tx] <= now.cost + 1) continue;
                        q.push(make_santa(ty, tx, now.cost+1));
                        visited[ty][tx] = now.cost+1;
                    }
                }
            }
        }
    }
    if (visited[sizeY][sizeX] == 987654321)
        return -1;
    else
        return visited[sizeY][sizeX];
}


int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>sizeY>>sizeX;
    for(int y=1; y<=sizeY; y++){
        for(int x=1; x<=sizeX; x++){
            string s;
            cin>>s;
            map[y][x] = stoi(s);
            if (map[y][x] >= 10)
                telpo[map[y][x]].push_back(make_pair(y, x));
            else if (map[y][x] == -2)
                gift_pos = make_pair(y, x);
        }
    }
    if (!find_gift(1, 1)){
        cout<<"-1";
        return 0;
    }
    cout<<go_dest(gift_pos.first, gift_pos.second, gift_cost);
}

// 다익스트라를 사용한 코드

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <queue>


using namespace std;


struct Santa{
    int y, x, cost;
    bool operator<(const Santa& other) const {
        return cost > other.cost;
    }
};
vector<vector<int> > map(501, vector<int>(501, 0));
vector<vector<pair<int, int> > > telpo(100001);
int moveY[4]={0,1,0,-1}, moveX[4]={1,0,-1,0}, sizeY=0, sizeX=0;
pair<int, int> gift_pos;


void print_telpo(){
    for(int i=0; i<telpo.size(); i++){
        if (telpo[i].size() == 0) continue;
        cout<<"i: "<<i<<" ";
        for(int j=0; j<telpo[i].size(); j++){
            cout<<telpo[i][j].first<<" "<<telpo[i][j].second<<"  ";
        }
        cout<<"\n";
    }
}


bool check_outside(int y, int x){
    return y < 1 || y > sizeY || x < 1 || x > sizeX;
}


Santa make_santa(int y, int x, int cost){
    Santa santa;
    santa.y = y;
    santa.x = x;
    santa.cost = cost;
    return santa;
}


int find_gift(int sy, int sx){
    vector<vector<int> >visited(501, vector<int>(501, 987654321));
    priority_queue<Santa> pq;
    pq.push(make_santa(sy, sx, 0));
    visited[sy][sx] = 0;
    while(!pq.empty()){
        Santa now = pq.top(); pq.pop();
        for(int d=0; d<4; d++){
            int ny = now.y + moveY[d];
            int nx = now.x + moveX[d];
            // 범위 밖 예외처리, 방문 예외처리, 벽 예외처리
            if (check_outside(ny, nx) || visited[ny][nx] <= now.cost || map[ny][nx] == 0) continue;
            // 선물인 경우
            if (map[ny][nx] == -2)
                return now.cost;
            // 빈칸이거나 텔레포트가 가능한 지역인 경우 -> 갈 수 있는 곳
            else if (map[ny][nx] == 0 || map[ny][nx] >= 10){
                pq.push(make_santa(ny, nx, now.cost));
                visited[ny][nx] = now.cost;
                // 텔레포트가 가능한 경우
                if (map[ny][nx] >= 10){
                    for(int i=0; i<telpo[map[ny][nx]].size(); i++){
                        int ty = telpo[map[ny][nx]][i].first;
                        int tx = telpo[map[ny][nx]][i].second;
                        // 이미 방문을 한 경우 -> pq 이기 때문에 걸어서 갈 수 있는 곳 or 이전에 텔포로 이동한 곳 제외
                        if (visited[ty][tx] <= now.cost + 1) continue;
                        pq.push(make_santa(ty, tx, now.cost+1));
                        visited[ty][tx] = now.cost + 1;
                    }
                }
            }
        }
    }
    return -1;
}


int go_dest(int y, int x, int cost){
    // 선물을 못 찾은 경우
    if (cost == -1)
        return -1;
    vector<vector<int> > visited(501, vector<int>(501, 987654321));
    priority_queue<Santa> pq;
    pq.push(make_santa(y, x, cost));
    visited[y][x] = cost;
    while(!pq.empty()){
        Santa now = pq.top(); pq.pop();
        for(int d=0; d<4; d++){
            int ny = now.y + moveY[d];
            int nx = now.x + moveX[d];
            // 범위 밖 예외처리, 방문 예외처리, 벽 예외처리
            if (check_outside(ny, nx) || visited[ny][nx] <= now.cost || map[ny][nx] == -1) continue;
            // 우하단인 경우 -> 도착지점
            if (ny == sizeY && nx == sizeX){
                return now.cost;
            }
            // 빈칸 or 선물이거나 텔레포트가 가능한 지역인 경우 -> 갈 수 있는 곳
            else if (map[ny][nx] == 0 || map[ny][nx] >= 10 || map[ny][nx] == -2){
                pq.push(make_santa(ny, nx, now.cost));
                visited[ny][nx] = now.cost;
                // 텔레포트가 가능한 경우
                if (map[ny][nx] >= 10){
                    for(int i=0; i<telpo[map[ny][nx]].size(); i++){
                        int ty = telpo[map[ny][nx]][i].first;
                        int tx = telpo[map[ny][nx]][i].second;
                        // 이미 방문을 한 경우 -> pq 이기 때문에 걸어서 갈 수 있는 곳 or 이전에 텔포로 이동한 곳 제외
                        if (visited[ty][tx] <= now.cost + 1) continue;
                        pq.push(make_santa(ty, tx, now.cost+1));
                        visited[ty][tx] = now.cost + 1;
                    }
                }
            }
        }
    }
    return -1;
}


int main(int argc, char** argv)
{
    cin>>sizeY>>sizeX;
    for(int y=1; y<=sizeY; y++){
        for(int x=1; x<=sizeX; x++){
            string s;
            cin>>s;
            int num = stoi(s);
            map[y][x] = num;
            if (map[y][x] == -2)
                gift_pos = make_pair(y, x);
            else if (map[y][x] >= 10){
                telpo[map[y][x]].push_back(make_pair(y, x));
            }
        }
    }
    cout<<go_dest(gift_pos.first, gift_pos.second, find_gift(1, 1));
}