[프로그래머스] level.3 - 경주로 건설(C++)

https://school.programmers.co.kr/learn/courses/30/lessons/67259

내 해답

#include <string.h>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

enum dir
{
    start = -1,
    right,
    down,
    left,
    up
};

struct road
{
    int x;
    int y;
    int coast;
    dir d;

    road()
    {
        x = 0;
        y = 0;
        coast = 0;
        d = dir::start;
    };

    road(int _x, int _y, int _coast, dir _d)
    {
        x = _x;
        y = _y;
        coast = _coast;
        d = _d;
    };
};

int solution(vector<vector<int>> board) {
	int answer = 1'000'000;
    int coast[25][25][4]; // 도로 건설 비용 방향별로 저장
    int dir_x[4] = { 1, 0 , -1, 0 }; // 우, 하, 좌, 상
    int dir_y[4] = {0, 1, 0, -1};
    
    // 비용을 최대 값으로 초기화 한다.
    for (int i = 0; i < 25; ++i)
        for (int j = 0; j < 25; ++j)
    	    memset(coast[i][j], 1'000'000, sizeof(int) * 4);

    // 시작점 Q에 넣기
    queue<road> q;
    for(int i= 0; i < 4; ++i)
	    coast[0][0][i] = 0;
    q.push(road());

    // Q가 빌 때까지 경로 탐색
    while (!q.empty())
    {
	    road cur = q.front();
	    q.pop();
        
        // 도착지점에 도착하면 최소 비용 저장
	    if (cur.y == board.size() - 1 && cur.x == board.size() - 1)
        {
	        answer = answer < cur.coast ? answer : cur.coast;
	        continue;;
        }
        
        // 4방향 탐색
	    for (int i = 0; i < 4; ++i)
        {
            int nx = cur.x + dir_x[i];
            int ny = cur.y + dir_y[i];
            
            // 다음 지점이 도로 범위 밖이면 continue
            if (nx < 0 || nx >= board.size() || ny < 0 || ny >= board.size())
                continue;
            
            // 다음 지점이 벽에 막혀있다면 continue
            if (board[ny][nx] == 1)
                continue;
            
            // 다음 지점 건설에 드는 비용 계산
            int c =  cur.coast + 100;
            
            // 코너라면 500원 추가
            if (cur.d != dir::start)
                if (cur.d % 2 != i % 2)
                    c += 500;
	        
            // 현재 방향에서 도로 건설 비용이 최소 값이라면 Q에 추가
            if (coast[ny][nx][i] >= c)
            {
	            coast[ny][nx][i] = c;
	            q.push(road(nx, ny, c, static_cast<dir>(i)));
            }
        }
    }

    return answer;
}

 

방향마다 건설 비용을 따로 저장해서 비교해야 하는 부분이 까다로운 문제였다.