프로그래머스 문제 - 경주로 건설

프로그래머스 경주로 건설 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

N X N 크기의 정사각형 격자 형태로 된 경주로가 주어집니다.
경주로는 0과 1로 채워져있으며 0은 길로 이동이 가능하고, 1은 벽으로 이동할 수 없습니다.
경주로에 도로를 설치하는데 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선도로 라고 하며, 두 직선 도로가 서로 직각으로 만나는 지점을 코너 라고 부릅니다.
출발점은 언제나 좌측 상단이며 도착점은 우측 하단입니다.
직선도로 하나에 100원, 코너 하나에 500원 추가일 때, 주로를 건설하는 데 필요한 최소 비용을 구해야합니다.

문제 풀이

미로찾기 문제에 비용의 최솟값을 구하는 문제입니다.
경주로의 최대값은 25X25이지만 DFS로 답을 구할 시 시간초과가 나옵니다.

좀더 빠르게 결과를 내기 위해 dp배열에 최소 비용을 저장하며 탐색하는 방법이 있습니다. 하지만 직선도로와 코너에 따라서 비용이 다르기 때문에 움직이는 방향에 따라 비용 계산이 달라지게 됩니다.
이를 위해 각 방향에 따른 최소비용의 저장을 위해 3차원 배열을 사용하여 BFS를 진행시켜주었습니다.

3차원 배열은 dp[x좌표값][y좌표값][각 방향의 비용] 으로 저장해주었습니다.
각 움직이는 방향으로 값들을 계산 및 최소값을 저장하며 모든 탐색을 끝낸 후 도착 지점의 4방향 중 최솟값이 정답이 됩니다.

BFS를 사용할 때 주의해야 할 점은 이미 검색했던 위치를 다시 검색하는 경우가 있으므로 들렸던 위치를 따로 저장해줄 필요가 없습니다.
그래도 아무 조치도 안 할 경우 무한으로 탐색을 진행하기 때문에, dp배열의 값과 계산하고 있는 값을 비교하여 dp배열의 값이 더 클 경우 이후에 더 계산할 필요가 없으므로 넘어가주면 알맞게 탐색을 끝낼 수 있습니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int INF = 2100000000;

int solution(vector<vector<int>> board) {
    int answer = INF;
    //[0] : x좌표, [1] : y좌표, [2] : 방향
    int direction[4][3] = {{0, 1, 0}, {1, 0, 1}, {0, -1, 2}, {-1, 0, 3}};
    int n = board.size();
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(4, INF))); 
    queue<vector<int>> q;
    
    q.push({0, 0, 0, 0});
    q.push({0, 0, 0, 1});
    while(!q.empty())
    {
        vector<int> cur = q.front();    q.pop();
        int x = cur[0];
        int y = cur[1];
        int cost = cur[2];
        int dir = cur[3];
        for(int i = 0; i < 4; i++)
        {
            //계산해도 되는 부분인지 확인
            if(x+direction[i][0] < 0 || x+direction[i][0] >= n || y+direction[i][1] < 0 || y+direction[i][1] >= n)
                continue;
            
            //맵에 통행 가능한 부분만 검색
            if(board[x+direction[i][0]][y+direction[i][1]] == 0)
            {
                int newCost = cost+100;
                if(dir != direction[i][2])
                {
                    newCost += 500;
                }
                //현재 계산한 값보다 dp값이 더 클 경우
                if(dp[x+direction[i][0]][y+direction[i][1]][direction[i][2]] > newCost)
                {
                    dp[x+direction[i][0]][y+direction[i][1]][direction[i][2]] = newCost;
                    //도착지점일경우 queue에 저장X
                    if(x+direction[i][0] == n-1 && y+direction[i][1] == n-1)
                        continue;
                    q.push({x+direction[i][0], y+direction[i][1], newCost, direction[i][2]});
                }
            }
        }
    }
    //도착지점의 4방향 탐색 후 최솟값 반환
    for(int i = 0; i < 4; i++)
    {
        answer = min(answer, dp[n-1][n-1][i]);
    }
    
    return answer;
}

출저

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