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

# 문제

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

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

 

# 실패 기록

BFS와 DFS 둘 중에 어떤 방법으로 풀지 고민하다가, 자동차의 방향이 바뀔 때마다 비용이 바뀌기 때문에 DFS 재귀함수에 자동차의 방향값을 인자로 넘겨줘야겠다고 생각했다. DFS를 사용해서 풀었던 코드는 다음과 같다. 그런데 시간 초과가 났다.

/*
  DFS 사용, 효율성 테스트 통과 못함.
*/

#include <string>
#include <vector>

using namespace std;

int min_cost = 0x7fffffff; // INT_MAX
int dir_r[4] = {-1, 0, 1, 0};
int dir_c[4] = {0, 1, 0, -1};
bool visited[25][25];

void dfs(vector<vector<int>> board, int n, int r, int c, int cost, int head) {
    if(r == n - 1 && c == n - 1) {
        if (cost < min_cost) min_cost = cost;
        return;
    }
    
    for (int i = 0; i < 4; i++) {
        int next_r = r + dir_r[i];
        int next_c = c + dir_c[i];
        if (next_r >= 0 && next_r < n && next_c >= 0 && next_c < n
            && board[next_r][next_c] == 0
            && !visited[next_r][next_c]) {
            visited[next_r][next_c] = true;
            if (i == head || (r == 0 && c == 0)) {
                dfs(board, n, next_r, next_c, cost + 100, i);
            }
            else {
                dfs(board, n, next_r, next_c, cost + 600, i);
            }
            visited[next_r][next_c] = false;
        }
    }
}

int solution(vector<vector<int>> board) {
    int n = board.size();
    
    visited[0][0] = true;
    dfs(board, n, 0, 0, 0, 0);
    
    return min_cost;
}

 

#  풀이 코드

BFS로 풀되, 자동차 구조체를 만들어서 방향값을 저장해주는 방식으로 풀었더니 통과할 수 있었다.

github 링크: github.com/ohohoi/algorithm-study

#include <vector>
#include <queue>
#include <cstdlib>

using namespace std;

struct Car {
    int r, c, dir, cost;
};

int min_cost = 0x7fffffff;
int dir_r[4] = {-1, 0, 1, 0};
int dir_c[4] = {0, 1, 0, -1};

int solution(vector<vector<int>> board) {
    int n = board.size();
    queue<Car> q;
    q.push({0, 0, 5, 0});
    board[0][0] = 1;

    while(!q.empty()) {
        Car car = q.front();
        q.pop();

        int cost = car.cost;

        if (car.r == n - 1 && car.c == n - 1) {
            if (cost < min_cost) min_cost = cost;
            continue;
        }

        for (int i = 0; i < 4; i++) {
            if (abs(i - car.dir) == 2) continue;

            int next_r = car.r + dir_r[i];
            int next_c = car.c + dir_c[i];

            if (next_r >= 0 && next_r < n && next_c >= 0 && next_c < n
                && board[next_r][next_c] != 1) {

                int new_cost = cost;
                if (i == car.dir || (car.r == 0 && car.c == 0)) new_cost += 100;
                else new_cost += 600;

                if (board[next_r][next_c] == 0 || board[next_r][next_c] >= new_cost) {
                    q.push({next_r, next_c, i, new_cost});
                    board[next_r][next_c] = new_cost;
                }
            }
        }
    }

    return min_cost;
}