경주로 건설(DP)

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

프로그래머스

 

해당 문제에서 고려해야 하는 점은 x, y 좌표뿐 아니라 해당 좌표에서 들어오게 된 경로, 즉 방향까지 고려야하여야 한다.

특정 좌표에서 특정 방향으로 접근했을때의 도로의 최소 건설 비용을 저장하는 방법의 DP 접근을 사용한다.

 

DP[x][y][direction] = x, y좌표의 지점에서 direction 방향으로 접근했을때 건설한 도로의 최소 비용

 

만약 현재 노드에서 동쪽으로 다음 노드에 접근한다면 다음과 같이 4가지 방법의 접근법이 고려된다.

 

1. 현재 좌표에서 동쪽으로 들어온 다음 동쪽으로 나감

> 불가능한 방법(나올 수 없는 방법)이므로 고려하지 않는다.

 

2. 현재 좌표에서 서쪽으로 들어온 다음 동쪽으로 나감

> 현재 좌표로 들어온 방향(서)과 다음 좌표에서 들어온 방향(서, 다음 좌표 기준)이 동일함

> 직선 도로이므로 100의 비용이 추가된다.

 

3, 4. 현재 좌표에서 북, 남쪽으로 들어온 다음 동쪽으로 나감

> 현재 좌표로 들어온 방향(북, 남)과 다음 좌표에서 들어온 방향(서)이 동일하지 않음

> 코너가 형성되므로 600의 비용이 추가된다.

 

현재 탐색중인 좌표로 들어온 방향과 다음 좌표의 기준으로 들어온 방향이 동일하면 현재 탐색중인 좌표의 DP값에 100을 추가하고 아니라면 600을 추가한다.

이렇게 나온 비용을 기존에 저장된 비용값과 비교하여 더 작은 값을 선택하도록 하면 된다.

 

BFS의 큐에 저장되는 정보는 {x좌표, y좌표, 들어온 방향}이 될 것이다.

 

최종적으론 도착지에 저장된 정보 중(동서남북 각각 진입 시) 가장 작은 값을 선택하면 된다.

 

#include <string>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

int xpos[4] = { 0, 0, -1, 1 };
int ypos[4] = { -1, 1, 0, 0 };
int DP[25][25][4] = { 0, };
int N;

bool checkpos(int x, int y)
{
    return 0 <= x && x <= N && 0 <= y && y <= N;
}

void BFS(int x, int y, vector<vector<int>>& board)
{
    queue<pair<pair<int, int>, int>> q;
    q.push({ {x, y}, 1 });
    q.push({ {x, y}, 3 });
    while (!q.empty())
    {
        int curx = q.front().first.first;
        int cury = q.front().first.second;
        int direction = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            // 온 방향: 0동 1서 2남 3북
            int nextx = curx + xpos[i];
            int nexty = cury + ypos[i];
            if (checkpos(nextx, nexty) && board[nextx][nexty] == 0)
            {
                int nextcost;
                if (i == direction) nextcost = DP[curx][cury][direction] + 100;
                else nextcost = DP[curx][cury][direction] + 600;
                if (DP[nextx][nexty][i] == -1 || nextcost < DP[nextx][nexty][i])
                {
                    DP[nextx][nexty][i] = nextcost;
                    q.push({ {nextx, nexty}, i });
                }
            }
        }
    }
}

int solution(vector<vector<int>> board)
{
    N = board.size() - 1;
    memset(DP, -1, sizeof(DP));
    DP[0][0][0] = 0;
    DP[0][0][1] = 0;
    DP[0][0][2] = 0;
    DP[0][0][3] = 0;
    BFS(0, 0, board);
    int answer = 987654321;
    for (int i = 0; i < 4; i++)
    {
        if (DP[N][N][i] != -1) answer = min(answer, DP[N][N][i]);
    }
    return answer;
}