[2020 카카오 인턴] 경주로 건설 (C++)

2020 카카오 인턴 코테 문제

5시간을 잡고 실전처럼 진행하였으며 코드의 최적화나 알고리즘은 정확하지 않음.

---

코딩테스트 연습 - 경주로 건설 | 프로그래머스 (programmers.co.kr)

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

---

4번문제였으며, 남은 1시간 30분 모두 빡빡하게 썻다.

bfs로 풀었다. 다만 여기선 전의 방향이 추가로 필요하였다.

#include <iostream>

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

using namespace std;

typedef struct pos {
    int x;
    int y;
    int cost;
    int dir;
}pos;

int ROTATE_X[] = { -1, 0, 1, 0 };
int ROTATE_Y[] = { 0, 1, 0, -1 };

int solution(vector<vector<int>> board) {
    int answer = 987654321;
    int N = board.size();
    queue<pos> q;
    vector<vector<vector<int>>> map(4, vector<vector<int>>(N, vector<int>(N, 987654321)));
    q.push({ 0, 0, 0, 1 });
    q.push({ 0, 0, 0, 2 });
    map[1][0][0] = 0;
    map[2][0][0] = 0;
    pos cur;
    

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

        if (cur.x == N - 1 && cur.y == N - 1)
        {
            answer = min(answer, cur.cost);
            continue;
        }

        for (int i = 0; i < 4; i++)
        {
            int next_row = cur.x + ROTATE_Y[i];
            int next_col = cur.y + ROTATE_X[i];

            if (next_row < 0 || next_col < 0 || next_row >= N || next_col >= N || board[next_row][next_col] == 1)
                continue;

            int cur_cost;
            if (cur.dir == i)
                cur_cost = cur.cost + 100;
            else
                cur_cost = cur.cost + 600;

            if (map[i][next_row][next_col] >= cur_cost)
            {
                map[i][next_row][next_col] = cur_cost;
                q.push({ next_row, next_col, cur_cost, i });
            }

        }
    }
    return answer;
}