[프로그래머스, C++] 경주로 건설

문제 링크

코딩테스트 연습 - 경주로 건설

 

 

 

풀이

블록 이동하기를 풀어서 그런지 비슷하게 풀었다.(다른 cost에 대해 중복 허용만 체킹)

 

// Car 구조체

행, 열, 방향, 비용

 

// 함수

isRange() : 보드 범위인지

isRoad() : 길인지

isArrive() : 도착했는지

isVisit() : 방문한건지 + 해당 비용보다 작을 경우는 방문 안한걸로(비용이 다르면 중복에 대해서 허용)

 

// BFS

반복문

{

무조건 Pop() --- 꺼내서 변수 할당 후 밑에 함수들 체크

1. 범위 체크

2. 길인지 체크

3. 도착했는지 체크

4. 방문 체크

무조건 Push() --- 이동은 cost+100 push(), 회전은 직진과 되돌아가기를 제외한 2가지에 대해 cost+500

}

 

 

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

using namespace std;

typedef struct Car{
    int row, col;       // 행, 열
    int dir;            // 방향(우:0, 하:1, 좌:2, 상:3)
    int cost;           // 비용
    Car(int _row, int _col, int _dir, int _cost){
        // 생성자
        row = _row;
        col = _col;
        dir = _dir;
        cost = _cost;
    }
}Car;

bool isRoad(int row, int col, vector<vector<int>> board){
    if(board[row][col] == 1) return false;
    return true;
}

bool isRange(int row, int col, int size){
    if(row < 0 || row >= size) return false;
    if(col < 0 || col >= size) return false;
    return true;
}

bool isArrive(int row, int col, int size){
    if(row == size-1 && col == size-1) return true;
    return false;
}

bool isVisit(int row, int col, int dir, int cost, vector<vector<vector<int>>>& visit){
    if(visit[row][col][dir] == 0){
        visit[row][col][dir] = cost;
        return false;
    }
    if(visit[row][col][dir] > cost){
        visit[row][col][dir] = cost;
        return false;
    }
    return true;
}

int solution(vector<vector<int>> board) {
    int answer = -1;
    
    // init
    const int size = board.size();
    int dirRow[] = {0, 1, 0, -1};       // 우, 하, 좌, 상
    int dirCol[] = {1, 0, -1, 0};       // 우, 하, 좌, 상
    vector<Car> cars;           // 도착한 경주차들
    
    // visit 컨테이너 할당
    vector<vector<vector<int>>> visit(size);
    for(int i=0; i<size; i++){
        visit[i].resize(size);
        for(int j=0; j<size; j++){
            visit[i][j].assign(4, 0);
        }
    }
    
    // BFS
    queue<Car> cq;
    cq.push(Car(0, 0, 0, 0));       // 우
    cq.push(Car(0, 0, 1, 0));       // 하
    
    while(!cq.empty()){
        // pop()
        int row = cq.front().row;
        int col = cq.front().col;
        int dir = cq.front().dir;
        int cost = cq.front().cost;
        
        cq.pop();
        if(!isRange(row, col, size)) continue;      // 범위인지
        if(!isRoad(row, col, board)) continue;      // 길인지
        if(isArrive(row, col, size)){               // 도착했는지
            // printf("(%d, %d), dir(%d), cost(%d)\n", row, col, dir, cost);
            cars.push_back(Car(row, col, dir, cost));
            continue;
        }
        if(isVisit(row, col, dir, cost, visit)) continue;     // 방문했었는지 + 비용이 다른지
        
        // 이동
        int destRow = row + dirRow[dir];
        int destCol = col + dirCol[dir];
        cq.push(Car(destRow, destCol, dir, cost+100));      // push()
        
        // 회전(뒤로 이동 X)
        int dir1 = (dir+1) % 4;
        int dir2 = (dir+3) % 4;
        cq.push(Car(row, col, dir1, cost+500));        // push()        
        cq.push(Car(row, col, dir2, cost+500));        // push()
    }
    // printf("\ncars(%d)\n", (int)cars.size());
    
    for(int i=0; i<cars.size(); i++){
        if(cars[i].cost < (unsigned int)answer)
            answer = cars[i].cost;
    }
    return answer;
}