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

프로그래머스, 2020 카카오 인턴십

 

문제 링크

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

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

---

C++ 풀이 (BFS)

#include <vector>
#include <queue>
using namespace std;

struct Car {
    int x, y;
    int current_direction; //0:왼쪽, 1:오른쪽, 2:위, 3:아래
    int cost; //누적 코스트
};

int solution(vector<vector<int>> board) {
    board[0][0] = -1;
    int N = board.size();
    int min_cost = 99999999;
    int mx[] = { 0, 0, -1, 1 }, my[] = { -1, 1, 0, 0 }; //왼쪽, 오른쪽, 위, 아래
    queue <Car> q;

    if (board[0][1] == 0) { //장애물 없을 경우 오른쪽 방향 스타트 추가
        q.push({ 0, 1, 1, 100 });
        board[0][1] = 100;
    }
    if (board[1][0] == 0) { //장애물 없을 경우 아래 방향 스타트 추가
        q.push({ 1, 0, 3, 100 });
        board[1][0] = 100;
    }   

    while (!q.empty()) {
        Car c = q.front();
        q.pop();
        if ((c.x == N - 1) && (c.y == N - 1)) {
            if (c.cost < min_cost)
                min_cost = c.cost;
            continue;
        }
        for (int i = 0; i < 4; i++) {
            int new_x = c.x + mx[i];
            int new_y = c.y + my[i];

            //범위 초과이거나 장애물이 있는 경우
            if ((new_x < 0) || (new_y < 0) || (new_x >= N) || (new_y >= N) || (board[new_x][new_y] == 1))
                continue;

            int new_cost = c.cost + 100;
            if (c.current_direction != i)
                new_cost += 500;

            // 장애물이 없고 방문한 적이 없거나, 새로 계산한 가격이 이전 기록한 값보다 작거나 같은 경우
            // queue에 추가 및 가격 갱신
            if ((board[new_x][new_y] == 0) || (new_cost <= board[new_x][new_y])) {
                Car d{ new_x, new_y, i, new_cost};
                q.push(d);
                board[new_x][new_y] = new_cost;
            }
        }
    }
    return min_cost;
}

 

처음 풀이 시 DFS로 풀었으나, 시간 초과가 나서 BFS로 다시 풀었다.

DFS로 풀었을 때는 재방문에 대한 조건 처리가 부족하여 시간 초과가 난 것으로 생각한다.

 

카카오 공식 풀이와 다른 분들의 풀이를 참고하니, 최단 거리를 찾기 위해 BFS를 이용했음을 알게되어 공부하고 다시 BFS로 풀어보았다.

또, 재방문에 대한 조건 처리와 메모이제이션을 활용하여 DFS로 푸신 분들의 코드에서도 방법을 배웠다.🤓

 

공부를 하니 시간이 참 빨리간다.

 

 

카카오 공식 해설 사이트

tech.kakao.com/2020/07/01/2020-internship-test/

2020 카카오 인턴십 for Tech developers 문제해설

 

C++ 풀이 (DFS, 시간 초과)

#include <string>
#include <vector>
using namespace std;

int min_coast;
vector<vector<int>> g_board;
int board_size;

// 0 : 오른쪽, 1 : 아래, 2 : 왼쪽, 3 : 위
void find_route(int x, int y, int direction, int current_cost, vector<vector<bool>> board_visit_check) {
    if (current_cost >= min_coast)
        return;
    if ((x == g_board.size() - 1) && (y == g_board.size() - 1)) {
        if (current_cost < min_coast)
            min_coast = current_cost;
        return;
    }
    //오른쪽
    if ((y + 1 < board_size) && (board_visit_check[x][y + 1] == false) && (g_board[x][y + 1] == 0)) {
        int temp_coast = current_cost;
        if (direction != 0)
            temp_coast += 500;
        temp_coast += 100;
        board_visit_check[x][y + 1] = true;
        find_route(x, y + 1, 0, temp_coast, board_visit_check);
        board_visit_check[x][y + 1] = false;
    }
    //아래
    if ((x + 1 < board_size) && (board_visit_check[x + 1][y] == false) && (g_board[x + 1][y] == 0)) {
        int temp_coast = current_cost;
        if (direction != 1)
            temp_coast += 500;
        temp_coast += 100;
        board_visit_check[x + 1][y] = true;
        find_route(x + 1, y, 1, temp_coast, board_visit_check);
        board_visit_check[x + 1][y] = false;
    }

    //왼쪽
    if ((y - 1 >= 0) && (board_visit_check[x][y - 1] == false) && (g_board[x][y - 1] == 0)) {
        int temp_coast = current_cost;
        if (direction != 2)
            temp_coast += 500;
        temp_coast += 100;
        board_visit_check[x][y - 1] = true;
        find_route(x, y - 1, 2, temp_coast, board_visit_check);
        board_visit_check[x][y - 1] = false;
    }

    //위
    if ((x - 1 >= 0) && (board_visit_check[x - 1][y] == false) && (g_board[x - 1][y] == 0)) {
        int temp_coast = current_cost;
        if (direction != 3)
            temp_coast += 500;
        temp_coast += 100;
        board_visit_check[x - 1][y] = true;
        find_route(x - 1, y, 3, temp_coast, board_visit_check);
        board_visit_check[x - 1][y] = false;
    }
    return;
}



int solution(vector<vector<int>> board) {
    min_coast = 99999999;
    g_board = board;
    board_size = board.size();
    vector <bool> temp(board_size, false);
    vector<vector<bool>> board_visit_check;
    for (int i = 0; i < board_size; i++)
        board_visit_check.push_back(temp);

    if (board[0][1] == 0) {
        board_visit_check[0][1] = true;
        find_route(0, 1, 0, 100, board_visit_check);
        board_visit_check[0][1] = false;
    }
        
    if (board[1][0] == 0) {
        board_visit_check[1][0] = true;
        find_route(1, 0, 1, 100, board_visit_check);
        board_visit_check[1][0] = false;
    }
    return min_coast;
}