경주로 건설 [Lv. 3] (C++)

프로그래머스

출발지 ~ 목적지까지 최소 비용으로 길을 만드는 문제입니다.

직선 길은 비용 100이 발생하며 코너를 만드는 비용은 500이 발생합니다.

 

풀이 방법

이 문제는 길 찾기 응용문제입니다.

단순하게 길을 탐색하는 문제가 아니라 직선, 코너와 같은 특별한 조건이 붙어서 복잡하게 느껴질 수 있습니다.

하지만 핵심은 길 찾기 그 이상도 그 이하도 아니라는 것입니다.

 

그렇기 때문에 최단 경로 탐색 알고리즘을 바탕으로 코드를 작성하고

조건(직진, 코너)을 부여하여 문제를 해결해 주면 됩니다.

 

- 조건 해결법

저는 조건을 type 변수로 해결하였습니다.

이전 노드에서 현재 노드가 Y축 이동이라면 0, X축 이동이라면 1로 type을 지정하였고

이전 type과 현재 type이 같다면 직진으로 판단, 그렇지 않다면 코너로 판단하여 비용을 업데이트하였습니다.

예시)

while (!q.empty())
{
    auto [cost, cy, cx, type] = q.top(); q.pop();
    cost *= -1;

    for (int i = 0; i < 4; i++)
    {
        int ny = cy + dy[i];
        int nx = cx + dx[i];
        if (!CHECK(board, ny, nx))
            continue;

		// 
        int nextType = ny == cy ? 1 : 0;
        int nextCost = nextType == type ? cost + 100 : cost + 600;
...
...
...

 

- 비용 업데이트 문제

비용을 업데이트하는 부분에서 어려움을 느낄만한 문제가 하나 있습니다.

 

특정 위치로 가기위한 경로A를 이용할 때 300, 경로B를 이용할 때는 500의 비용이 발생한다고 가정하겠습니다.

이때 더 적은 비용인 A경로가 더 적합하게 느껴질 수 있지만

A경로 이후에 코너를 만들어야 한다면 A경로는 800, B경로는 600으로 비용이 역전되는 문제가 발생합니다.

 

그렇기 때문에 Y축으로 이동했을 때의 비용과 X축으로 이동했을 때의 비용을 따로 기록하여

최종적으로 목적지에 도착했을 때 가정 적은 비용을 출력하는 방향으로 코드를 작성해주어야 합니다.

 

예시)

vector<vector<int>> dist0(board.size(), vector<int>(board[0].size(), 1000000000));
vector<vector<int>> dist1(board.size(), vector<int>(board[0].size(), 1000000000));

// 비용, Y, X, 타입
priority_queue<tuple<int, int, int, int>> q;
q.push({0, 0, 0, 0});
q.push({0, 0, 0, 1});  
dist0[0][0] = 0;
dist1[0][0] = 0;

...
...
...

if (nextType == 0 && dist0[ny][nx] > nextCost)
{
    dist0[ny][nx] = nc;
    q.push({-(nextCost), ny, nx, nextType});
}
else if (nextType == 1 && dist1[ny][nx] > nextCost)
{
    dist1[ny][nx] = nc;
    q.push({-(nextCost), ny, nx, nextType});
}

 

 

정답코드

#include <string>
#include <vector>
#include <queue>
#include <tuple>
#include <iostream>
using namespace std;
 
bool CHECK(vector<vector<int>>& board, int y, int x)
{
    return y >= 0 && y < board.size() && x >= 0 && x < board[y].size() && board[y][x] == 0;
}
 
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};
int dijkstra(vector<vector<int>>& board)
{
    vector<vector<int>> dist0(board.size(), vector<int>(board[0].size(), 1000000000));
    vector<vector<int>> dist1(board.size(), vector<int>(board[0].size(), 1000000000));
    dist0[0][0] = 0;
    dist1[0][0] = 0;
 
    priority_queue<tuple<int, int, int, int>> q;
    q.push({0, 0, 0, 0});
    q.push({0, 0, 0, 1});  
 
    
    while (!q.empty())
    {
        auto [cost, cy, cx, type] = q.top(); q.pop();
        cost *= -1;
 
        for (int i = 0; i < 4; i++)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if (!CHECK(board, ny, nx))
                continue;
            
            int nextType = ny == cy ? 1 : 0;
            int nextCost = nextType == type ? cost + 100 : cost + 600;
            
            if (nextType == 0 && dist0[ny][nx] > nextCost)
            {
                dist0[ny][nx] = nextCost;
                q.push({-(nextCost), ny, nx, nextType});
            }
            else if (nextType == 1 && dist1[ny][nx] > nextCost)
            {
                dist1[ny][nx] = nextCost;
                q.push({-(nextCost), ny, nx, nextType});
            }
        }
    }
 
    int y = board.size() - 1;
    int x = board[0].size() - 1;
    return min(dist0[y][x], dist1[y][x]);
}
 
int solution(vector<vector<int>> board) {
    return dijkstra(board);
}