[programmers] Lv.3 경주로 건설(c++)

#include <string>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Node{
    int x, y;
    int cost;
    int dir;

    Node(int x=0, int y=0, int cost=0, int dir=4) : x{x}, y{y}, cost{cost}, dir{dir}{}
};

int solution(vector<vector<int>> board) {
    vector<int> x_dir = {-1, 1, 0, 0};
    vector<int> y_dir = {0, 0, -1, 1};
    vector<vector<int>> possible_dir = {{0, 2, 3}, {1, 2, 3}, {0, 1, 2}, {0, 1, 3}, {1, 3}};
    int N = board.size();
    vector<vector<vector<int>>> dp(N, vector<vector<int>>(N, vector<int>(4, 0)));
    
    queue<Node*> que;
    que.push(new Node());
    while(!que.empty()){
        Node* bf = que.front();
        que.pop();

        for(int dir : possible_dir[bf->dir]){
            Node* cur = new Node(bf->x + x_dir[dir], bf->y + y_dir[dir], bf->cost, dir);
            if(cur->x >= 0 && cur->x < N && cur->y >= 0 && cur->y < N
              && board[cur->x][cur->y] == 0){
                cur->cost += (dir == bf->dir || bf->cost == 0)? 100 : 600;

                if(dp[cur->x][cur->y][dir] == 0 || cur->cost < dp[cur->x][cur->y][dir])
                    dp[cur->x][cur->y][dir] = cur->cost;
                else continue;
                
                if(cur->x == N-1 && cur->y == N-1) continue;
                else que.push(cur);
            }
        }
    }
    int answer = INT_MAX;
    for(auto ele : dp[N-1][N-1])
        if(answer > ele && ele != 0) answer = ele;
    return answer;
}

---

문제

https://programmers.co.kr/learn/courses/30/lessons/67259

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

728x90

---

[접근]

BFS+DP

BFS

https://jolly-note.tistory.com/63

BFS (Breadth First Search, 너비 우선 탐색)

DP(링크 추가 예정)

---

[접근1]

Node structure을 만들어 해당 커서의 위치, 비용, 전 칸에서 왔을때의 방향을 기록한다.

struct Node{
    int x, y;
    int cost;
    int dir;

    Node(int x=0, int y=0, int cost=0, int dir=4) : x{x}, y{y}, cost{cost}, dir{dir}{}
};

---

[접근2]

이동을 위한 x_dir, y_dir 선언.

진행방향의 정 반대로 갈 일은 없기 때문에, 각 방향에 대하여 갈 수 있는 방향을 정해주었다.

board size를 매번 접근하기보단 정수 N을 선언하여 대입하였고, 쉽게 사용할 수 있게 해주었다.

dp에는 각 좌표에서 각 (전 칸에서 들어오게된)방향에따른 cost를 저장하는 용도이다.

vector<int> x_dir = {-1, 1, 0, 0};
vector<int> y_dir = {0, 0, -1, 1};
vector<vector<int>> possible_dir = {{0, 2, 3}, {1, 2, 3}, {0, 1, 2}, {0, 1, 3}, {1, 3}};
int N = board.size();
vector<vector<vector<int>>> dp(N, vector<vector<int>>(N, vector<int>(4, 0)));

---

[접근3]

Node가 들어가는 queue를 만들어 BFS 준비를 하고 제일 첫 Node를 집어넣어준다.

첫 노드의 좌표는 0, 0이며 cost는 0에서 시작하고, dir은 4로 주어서 오른쪽과 아래, 두 방향으로 출발할 수 있게 하였다.

que에서 하나를 꺼내어 bf에 저장한다.

이 노드의 좌표에서 가능한 방향을 돌면서 새로운 좌표와 전 cost와 진행 방향을 대입하여 새로운 노드를 선언한다.

범위 내의 좌표이고 막혀있지 않으면 현재 노드의 cost에 전의 방향과 같으면 직진이므로 100을 다르면 코너이므로 100+500을 더한다.

만약 dp에서 해당 좌표의 해당 방향이 0이거나 해당 좌표의 해당방향의 cost보다 현재 cost가 더 작다면 해당좌표의 해당 방향에 현재 cost를 대입해준다.

만약 현재 좌표의 위치가 도착지점이라면 que에 현재 노드를 push하지 않고 넘어가고 도착지점이 아니라면 현재 노드를 push해준다.

이 방법을 que가 빌때까지 반복해준다.

queue<Node*> que;
que.push(new Node());
while(!que.empty()){
    Node* bf = que.front();
    que.pop();

    for(int dir : possible_dir[bf->dir]){
        Node* cur = new Node(bf->x + x_dir[dir], bf->y + y_dir[dir], bf->cost, dir);
        if(cur->x >= 0 && cur->x < N && cur->y >= 0 && cur->y < N
          && board[cur->x][cur->y] == 0){
            cur->cost += (dir == bf->dir || bf->cost == 0)? 100 : 600;

            if(dp[cur->x][cur->y][dir] == 0 || cur->cost < dp[cur->x][cur->y][dir])
                dp[cur->x][cur->y][dir] = cur->cost;
            else continue;

            if(cur->x == N-1 && cur->y == N-1) continue;
            else que.push(cur);
        }
    }
}

---

[접근4]

answer 변수에 INT_MAX를 대입하여 선언해주고

dp의 맨 마지막 좌표의 모든 방향에 대한 cost를 돌며

answer의 값보다 작거나 0이 아닐 때, answer에 대입해준다.

int answer = INT_MAX;
for(auto ele : dp[N-1][N-1])
    if(answer > ele && ele != 0) answer = ele;
return answer;