[알고리즘문제] 프로그래머스 - 경주로 건설

먼저 최소비용 문제이기 때문에 bfs를 사용했습니다. 처음 23점을 맞고, 코드를 분석하는데 상하좌우 탐색할 때 더 많은 비용을 사용함에도 먼저 탐색했기 때문에 그 경로를 사용하는 오류가 있었습니다. 그래서 이 부분을 해결하는 방법은 다른분의 코드를 참고하였는데, arr[][]에 해당 지점에서의 최소비용을 저장하는 것입니다.

 

그래서 [4,5]에 방문했을 때 현재 계산된 값이 arr[4][5]에 저장된(이전에 누군가가 방문했을 때의 값)보다 더 작은 경우 arr[4][5]의 값을 갱신해 줍니다. 그리고 그때의 x,y, 방향, sum값을 저장합니다. 기존에는 [0,0]에서 오른쪽과 아래로 이동했을 경우 따로 구했는데 각 지점의 최소비용을 계속 갱신해 주는 방법이라면 그냥 [0,0]에서 시작해도 됩니다.

 

그리고 직선도로인지 커브인지 확인하는 것은 각 위치의 현재, 과거위치를 저장하고 과거위치와 새로운 위치를 비교하여 x,y값이 하나라도 같으면 직선도로라 생각했는데, 물론 맞았지만 그보다 0,1,2,3값을 저장해서 그 값이 같은지 비교하면 더 간단합니다.

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

int height, width;
int answer = 987654321;
using namespace std;
int arr[26][26];

// 위 왼쪽 아래 오른쪽
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

struct Info
{
    int x;
    int y;
    int sum;
    int dir;
};

void bfs()
{
    queue<Info> que;
    que.push({0, 0, 0, -1});
    arr[0][0] = 1;

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

        if (cur.x == width - 1 && cur.y == height - 1)
        {
            answer = min(answer, cur.sum);
        }

        for (int i = 0; i < 4; i++)
        {
            int newY = cur.y + dy[i];
            int newX = cur.x + dx[i];

            if (newY >= 0 && newX >= 0 && newY < height && newX < width && arr[newY][newX] != 1) // 탐색을 할 수 있는 영역
            {
                int nextSum = 0;

                if (cur.dir == -1 || cur.dir == i) // -1인 이유는, 0,0위치에서는 직선으로 밖에 움직이지 못하기 때문
                {
                    nextSum = cur.sum + 100;
                }
                else
                {
                    nextSum = cur.sum + 600;
                }

                if (arr[newY][newX] == 0 || arr[newY][newX] >= nextSum) // 처음 방문한곳이거나, 건설비용이 더 적은 길을 발견하면 원래 값을 갱신
                {
                    arr[newY][newX] = nextSum;
                    que.push({newX, newY, nextSum, i});
                }
            }
        }
    }
}

int solution(vector<vector<int>> board)
{
    height = board.size();
    width = board[0].size();

    for (int y = 0; y < board.size(); y++)
    {
        for (int x = 0; x < board[y].size(); x++)
        {
            arr[y][x] = board[y][x];
        }
    }
    bfs();
    return answer;
}