리코쳇 로봇 - 프로그래머스

문제 

문제 난이도 : 프로그래머스 2단계 

문제 정답률 : 42%

문제 분류: BFS, DFS, 다익스트라(내 풀이)

문제 리뷰

복잡복잡하다.

다익스트라 살짝 응용된 버전

PQ에 comp랑 Point struct 빠르게 구현할 수 있어야겠다.

내일 넥토리얼 코딩테스트를 본다.

못 풀겠는건 포기하고 최대한 풀 수 있도록 해야겠다. 

문제 소스코드

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
struct Point{
    int x;
    int y;
    Point(int a, int b){
        x = a;
        y = b;
    }
};
struct comp{
    bool operator()(pair<int, Point>& a, pair<int, Point>& b){
        return a.first > b.first;
    }
};
int Distance[101][101];
vector<pair<int,Point>> Edges[101][101];

void Dijkstra(int sx, int sy){
    for(int i = 0 ; i < 101; i++){
        for(int j = 0; j <101; j++){
            Distance[i][j] = 2100000000;
        }
    }
    Distance[sx][sy] = 0;
    priority_queue<pair<int, Point>, vector<pair<int, Point>>, comp> PQ;
    PQ.push({0, Point(sx,sy)});
    while(!PQ.empty()){
        pair<int, Point> pp = PQ.top();
        int CurDist = - pp.first;
        Point CurPoint = pp.second;
        PQ.pop();
        for(pair<int,Point> p : Edges[CurPoint.x][CurPoint.y]){
            Point NextPoint = p.second;
            int NextDist = p.first;
            if(Distance[NextPoint.x][NextPoint.y] > NextDist + CurDist){
                Distance[NextPoint.x][NextPoint.y] = NextDist + CurDist;
                PQ.push({-Distance[NextPoint.x][NextPoint.y], NextPoint});
            }
        }
    }
    
}


int solution(vector<string> board) {
    int answer = 0;
    pair<int,int> Goal = {-1,-1};
    pair<int,int> Start ={-1,-1};
    int nx =  board.size();
    int ny = board[0].size();
    for(int i = 0; i< board.size(); i++){
        for(int j = 0; j < board[i].size(); j++){
            if(board[i][j] == 'R'){
                Start = {i,j};
            }
            if(board[i][j] == 'G'){
                Goal = {i, j};
                continue;
            };
            if(board[i][j] == 'D') continue;
            //해당 지점에서 위로 갈 경우
            if(i > 0){
                for(int p = i - 1; p >= 0; p--){
                    if(board[p][j] == 'D'){
                        Edges[i][j].push_back({1, Point(p + 1, j)});
                        break;
                    }
                    if(p == 0){
                        Edges[i][j].push_back({1, Point(0, j)});
                        break;
                    }
                }
            }
            //아래로 갈 경우
            if(i < nx - 1){
                for(int p = i + 1; p <= nx - 1; p++){
                    if(board[p][j] == 'D'){
                        Edges[i][j].push_back({1, Point(p - 1, j)});
                        break;
                    }
                    if(p == nx-1){
                        Edges[i][j].push_back({1, Point(p, j)});
                        break;
                    }
                }
            }
            //해당 지점에서 왼쪽
            if(j > 0){
                for(int p = j - 1; p >= 0; p--){
                    if(board[i][p] == 'D'){
                        Edges[i][j].push_back({1, Point(i, p+1)});
                        break;
                    }
                    if(p == 0){
                        Edges[i][j].push_back({1, Point(i, 0)});
                        break;
                    }
                    
                }
            }
            //오른쪽
            if(j < ny - 1){
                for(int p = j + 1; p <= ny - 1; p++){
                    if(board[i][p] == 'D'){
                        Edges[i][j].push_back({1, Point(i, p-1)});
                        break;
                    }
                    if(p == ny-1){
                        Edges[i][j].push_back({1, Point(i, p)});
                        break;
                    }
                    
                }
            }
        }
    }
    Dijkstra(Start.first, Start.second);
    answer = Distance[Goal.first][Goal.second];
    if(answer == 2100000000){
        return -1;
    }
    return answer;
}