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

 

 

문제

소스코드

 

#include<vector>
#include<utility>
#include<queue>
 
constexpr int STRATE_COST   = 100;
constexpr int CURVE_COST    = 600;
constexpr int BOARD_SIZE    = 26;
constexpr int MAX_COST      = 9999999;
using Direction = std::pair<int, int>;
 
class CNode {
public:
    int         constructCost_;
    int         x_;
    int         y_;
    int         dir_;
};
 
int costed[BOARD_SIZE][BOARD_SIZE];
std::queue<CNode> queue;
 
int solution(std::vector<std::vector<int>> board) {
    int answer = MAX_COST;
    int goal = board.size() - 1;
    Direction direction[4] = { 
        Direction{-1,0},Direction{0,-1},
        Direction{1,0}, Direction{0,1} };
 
    for (int i = 0; i < BOARD_SIZE; ++i) {
        for (int j = 0; j < BOARD_SIZE; ++j) {
            costed[i][j] = MAX_COST;
        }
    }
 
    queue.emplace(CNode{ 0,0,0,-1 });
    //BFS
    while (queue.empty() == false) {
        int x = queue.front().x_;
        int y = queue.front().y_;
        int cost = queue.front().constructCost_;
        int dir = queue.front().dir_;
 
        queue.pop();
 
        if (x == goal && y == goal) {
            if (answer >= cost) {
                answer = cost;
            }
        }
 
        //Search(Left, Right, Down, Top)
        for (int i = 0; i < 4; ++i) {
 
            int dx = x + direction[i].first;
            int dy = y + direction[i].second;
 
            //Safe Check
            if ( (dx >= 0 && dx < board.size()) && (dy >= 0 && dy < board.size())) {
 
                //Move Able
                if (board[dx][dy] == 0) {
 
                    int newCost;
                    
 
                    //같은 방향
                    if ((i % 2) == (dir % 2) || dir == -1) {
                        newCost = cost + STRATE_COST;
                    }
                    else {
                        newCost = cost + CURVE_COST;
                    }
 
                    if (newCost <= costed[dx][dy]) {
                        costed[dx][dy] = newCost;
                        queue.emplace(CNode{ newCost,dx,dy,i });
                    }
                }
            }
        }
    }
    return answer;
}

후기

이 문제를 해결하기 위한 키워드는 BFS 혹은 다익스트라이다.

다익스트라를 이용해서 풀 수 있지만 여기서는 BFS를 이용해서 풀었다.

 

BFS/DFS 나 다익스트라 A*까지 구현해봐서 비교적 쉬울거라고 예상했지만 시간이 좀 걸렸던 문제였다.

시간이 걸린이유는 탐색알고리즘부분이 아니라 코너 부분을 어떻게 해결할 것인가 부분에서 시간이 꽤걸렸다.

 

처음에는 old_x, old_y 와 같이 탐색 전 노드와 비교해서 코너 여부를 판단했지만 쉽지 않아서 다른분들이 풀었던 방식을 조금 참조했는데 대부분 방향을 가지고 탐색을 시도하는 방식으로 풀어서 나도 그러한 방식으로 풀었다.

 

0(왼쪽), 1(아래), 2(왼쪽), 3(위) 이런식으로 방향이 있을 때 i%2와 dir%2가 같으면 같은 수평방향이며 다르면 수직이기 때문에 코너 가중치를 계산하도록 하였다. -1은 처음에는 직선만 하는 경우를 예외처리해서 넣은 경우이다.

 

 

처음 위치(원)에서 왼, 오른, 아래, 위 방향으로 (100+100)100씩 가중치를 더하고 여기서 화살표는 방향을 나타낸다.

 

그 다음 원에서 위쪽 방향으로 이동 후 다시 탐색을 시작할 때 위 방향이 아닌 왼쪽과 오른쪽은 (200+600)의 가중치를 더해서 Queue에 넣는 것을 확인할 수 있다.

 

문제에서 나오는 코너의 가중치는 500인대 600을 더하는 이유는 코너에 직선이 추가적으로 들어가기 때문이다.

 

 

* 만약 테스트 케이스 21,22번이 틀린다면 MAX_COST 값을 늘려보는걸 추천한다.

 

출처 및 레퍼런스

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/67259