[프로그래머스][2020 카카오 인턴십] 경주로 건설

문제

프로그래머스 2020 카카오 인턴십 - 경주로 건설 (Level 4)

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

 

---

문제 풀이

접근 방식

경주로를 건설하는 데 필요한 최소 비용을 구하는 문제이다.

이 문제는 BFS + DP의 방식으로 문제를 해결하였다.

 

우선 Node 구조체를 만들어 위치, 방향, 직선 개수, 코너 개수를 저장하여 우선순위 큐에 넣어주었다.

우선순위 큐는 비용이 적은 순으로 정렬될 수 있도록 설정해주었다.

또한 3차원 배열인 result를 만들어 각 방향별 최소 비용을 저장해주었다.

 

BFS는 (N-1, N-1) 위치에 왔을 때 종료되도록 구현하였다.

현재의 위치에서 갈 수 있는 방향은 현재 방향의 좌측, 현재 방향, 형재 방향의 우측으로 총 3가지이다.

그래서 이 3가지 방향으로 갈 수 있는지 확인해주었고, 현재 방향과 같은 방향인 경우에는 직선의 개수만 증가,

현재 방향과 다른 방향인 경우에는 직선과 곡선의 개수를 증가시켜서 큐에 넣어주며 탐색을 진행하였다.

 

---

풀이 코드 - C++

#include <vector>
#include <queue>

using namespace std;

struct Node{
    int x;
    int y;
    int d;
    int s;
    int c;
};

struct cmp{
    bool operator()(Node a, Node b) {
        return (a.s + a.c * 5) > (b.s + b.c * 5);
    }
};

int solution(vector<vector<int>> board) {
    int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    int len = board.size();
    int result[25][25][4];    
    for(int i = 0; i < len; i++) {
        for(int j = 0; j < len; j++){
            for(int k = 0; k < 4; k++) {                
                result[i][j][k] = 987654321;
            }
        }
    }    
    for(int i = 0; i < 4; i++) {                
        result[0][0][i] = 0;
    }
    
    priority_queue<Node, vector<Node>, cmp> q;
    if(board[0][1] == 0){
        q.push({0,1,0,1,0});
        result[0][1][0] = 100;
    }
    if(board[1][0] == 0) {
        q.push({1,0,1,1,0});
        result[1][0][1] = 100;
    }
    
    while(!q.empty()) {
        Node now = q.top(); q.pop();                
        if(now.x == len - 1 && now.y == len - 1)
            return result[now.x][now.y][now.d];        
        int cost = now.s * 100 + now.c * 500;
        if(result[now.x][now.y][now.d] < cost) continue;
        
        for(int i = now.d - 1; i <= now.d + 1; i++) {
            int dir = (4 + i) % 4;
            int nx = now.x + dirs[dir][0];        
            int ny = now.y + dirs[dir][1];
            
            if(nx < 0 || ny < 0 || nx >= len || ny >= len) continue;
            if(board[nx][ny] == 1) continue;
            
            if(now.d == dir && result[nx][ny][dir] >= cost + 100) {
                result[nx][ny][dir] = cost + 100;
                q.push({nx, ny, dir, now.s + 1, now.c});
            } else if(now.d != dir && result[nx][ny][dir] >= cost + 600) {
                result[nx][ny][dir] = cost + 600;
                q.push({nx, ny, dir, now.s + 1, now.c + 1});
            }
        }
    }
}

실행 결과

실행 결과 : 100.0