Programmers 경주로 건설

programmers 경주로 건설 : programmers.co.kr/learn/courses/30/lessons/67259

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

2020 카카오 인턴십에서 출제된 경주로 건설입니다.

Level 3에 해당하며, 기법으로는 다익스트라 알고리즘에 살짝(?)의 방향까지 생각해주셔야 합니다.

방향을 일방적으로 고려하시면 틀립니다!

 

이 문제에서 다익스트라를 구현할 실력이 되신다면 대부분 테스트케이스 14번?이 틀리게 될 것입니다.

14번 테스트케이스를 대략적으로 만들어보면 아래와 같습니다.

 

{0, 0, 0, 0, 0}

{0, 1, 1, 1, 0}

{0, 0, 1, 0, 0}

{1, 0, 0, 0, 1}

{0, 1, 1, 0, 0}

 

0,0을 기점으로 오른쪽으로 출발했을 때는 board[3][3]에서 2300을,

0,0을 기점으로 아래쪽으로 출발했을 때는 board[3][3]에서 2100을 갖게 될 것입니다.

 

당장 [3][3]에서 출발했을 때 2300을 기준으로 [4][4]에 도달하면 3000이 되고

2100을 기준으로 도달하면 3300이 됩니다.

'코너'가 한번 더 발생하기 때문입니다.

 

만약 방향을 일방적으로 고려한 다익스트라를 구현한다면,

[3][3]에서 2300을 꺼냈을 떄

다익스트라로 갱신한 최솟값 배열을 min_dist라고 한다면

이미 min_dist[3][3] 은 2100이기 때문에 continue되면서 탐색하지 않게 되겠죠,,

 

이정도 설명이면 충분히 이해하셨을 거라 생각합니다.

즉, 다익스트라를 통해 '그 지점의 방향'에 대한 최솟값을 가지고 계셔야 합니다.

min_dist[y][x][방향] 이렇게 3차원배열로 해결가능합니다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct pii {
    int dist, y, x, way;
};
struct piicmp {
    bool operator()(pii& A, pii& B) {
        return A.dist > B.dist;
    }
};

int my[4] = { -1,0,1,0 };
int mx[4] = { 0,1,0,-1 };
int arr[26][26][4];

int solution(vector<vector<int>> board) {
    int answer = 987654321;
    int bs = board.size();
    for (int i = 0; i < bs; i++) {
        for (int j = 0; j < bs; j++) {
            for(int k = 0; k<4; k++){
                arr[i][j][k] = 987654321;                
            }
        }
    }

    priority_queue<pii, vector<pii>, piicmp> pq;
    if (!board[0][1]) pq.push({ 0,0,0,1 });
    if (!board[1][0]) pq.push({ 0,0,0,2 });
    while (!pq.empty()) {
        int y = pq.top().y;
        int x = pq.top().x;
        int dist = pq.top().dist;
        int way = pq.top().way;
        pq.pop();

        if (arr[y][x][way] < dist) continue;
        if (y == bs - 1 && x == bs - 1) {
            answer = min(answer, dist);
        }

        for (int i = 0; i < 4; i++) {
            int yy = y + my[i];
            int xx = x + mx[i];
            if (yy >= 0 && yy < bs && xx >= 0 && xx < bs && board[yy][xx] != 1) {
                if (i == way) {
                    int distance = dist + 100;
                    if (distance < arr[yy][xx][i]) {
                        arr[yy][xx][i] = distance;
                        pq.push({ distance, yy, xx, way });
                    }
                }
                else if (i == (way + 1)%4 || i == (4 + way - 1)%4) {
                    int distance = dist + 600;
                    if (distance < arr[yy][xx][i]) {
                        arr[yy][xx][i] = distance;
                        pq.push({ distance, yy, xx, i });
                    }
                }
            }
        }
    }


    return answer;
}