[프로그래머스] 리코쳇 로봇 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

 

음.. 역시 요즘 코테 실력이 다들 상향평준화 된 것이 확실하다.

이정도 문제면 LV 3 줄만한데 2를 준 것을 보니..

 

이 문제는 BFS를 사용하는 것은 쉽다.

 

하지만 두개의 생각을 해내야한다.

 

첫번째는 방향타별로 체크로직을만들어야겠다.

하지만 같은 방향이어도 더 짧은길로 올 수 있으니 카운트도 샌다.

 

그리고 은근히 복잡도가 있는 로직을 잘 짠다

 

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

using namespace std;

queue<pair<pair<int, int>, pair<int, int>>> q;
int check[101][101][4];
int answer = 1000000001;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

int maxX;
int maxY;

bool range(int x, int y){
    return x > -1 && y > -1 && x < maxX && y < maxY ;
}

void bfs(vector<string> board, int strtx, int strty) {
    q.push({{strtx, strty}, {0 ,1}});
    q.push({{strtx, strty}, {1 ,1}});
    q.push({{strtx, strty}, {2 ,1}});
    q.push({{strtx, strty}, {3 ,1}});

    while(!q.empty()) {
        int x       = q.front().first.first;
        int y       = q.front().first.second;
        int forward = q.front().second.first;
        int cnt     = q.front().second.second;
        check[x][y][forward] = cnt;
        q.pop();    
        
        int forwardNextx = x + dx[forward];
        int forwardNexty = y + dy[forward];
        
        // 다음 방향이 벽이면 현재 도착했는지 확인
        if(!range(forwardNextx, forwardNexty) 
           || board[forwardNextx][forwardNexty] == 'D') {
            
            // 도착여부 체크
            if(board[x][y] == 'G') {
                answer = min(answer, cnt);
            } 
            // 도착안함
            else {
                for(int i = 0; i < 4; i++) {
                    int nextx = x + dx[i];
                    int nexty = y + dy[i];
                    int nextCnt = cnt + 1;

                    if(check[nextx][nexty][i] > nextCnt
                       && range(nextx, nexty)
                       && board[nextx][nexty] != 'D') {
                        q.push({{nextx, nexty}, {i, nextCnt}});
                    }
                }
            }
        }
        
        // 벽이 아니면 그대로 진행
        else {
            q.push({{forwardNextx, forwardNexty}, {forward, cnt}});
        }
        
    }
}

int solution(vector<string> board) {    
    int x;
    int y;
        
    for(int i = 0; i < board.size(); i++) {
        for(int j = 0; j < board[i].size(); j++){
            if(board[i][j] == 'R') {
                x = i;
                y = j;
            }
            
            for(int k = 0; k < 4; k++) {
                check[i][j][k] = 100010101010;
            }
        }
    }
    
    maxX = board.size();
    maxY = board[0].size();
    bfs(board, x, y);
    
    if(answer == 1000000001) answer = -1;
    
    return answer;
}