Programmers - 경주로 건설

---

title: Programmers - 경주로 건설
date: 2022-08-30
tags:

• Algorithm
• DP
• BFS

---

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

문제 요약

2차원 정사각형의 도면이 주어진다. 직선 도로는 100원, 90도로 꺾이는 도로는 500원이 추가로 든다.
길이 N일 때, (0,0)에서 (N-1,N-1) 까지 가는 도로를 설치할 때 최소 비용을 return한다.

문제 풀이

옛날에 시도하였다 실패한 문제이다.
Level 3의 문제를 많이 풀었으며, 남은 문제들 풀이에 실패할 경우 어느정도의 텀을 두고 다시 풀어야 하며, 지금이 실패한 문제를 풀기 적절한 시기라고 판단하였다.
과거의 풀이에 문제가 있어 실패를 하였기에 실패한 풀이는 아예 보지 않고 새로 풀었다.


DFS의 경우 최악의 경로부터 조금씩 개선이 될 경우 너무 많은 반복이 이루어지므로 BFS를 이용하였다.
방향이 바뀔 때 추가 비용이 들어가기에 각 위치마다 두 방향의 정보를 저장하도록 DP를 구성하였다.
수직과 수평 이동만 확인하며, 반대로 이동할 경우 비용이 높아져 무시하기에 네 방향마다 따로 구성하는 것 보다는 이것이 더 효율적이라 판단하였다.
priority_queue를 이용하여 금액이 낮은 경로부터 확인하며, 이동 가능한 위치에 대한 정보를 priority_queue에 넣으며 갱신한다.


놀랍게도 이 풀이가 끝이다.
분명 과거에 풀이할 때 실패하였는데, 너무 간단하게 성공하여 어이가 없다.

프로그램

#include <vector>
#include <queue>
#include <algorithm>

using std :: vector ;
using std :: priority_queue ;

struct mapInfo
{
    int iX ;
    int iY ;
    int iDirection ;
    int iCost ;
} ;

struct comp
{
   bool operator () ( mapInfo & a , mapInfo & b )
   {
       return a.iCost > b.iCost ;
   }
} ;

int solution ( vector < vector < int > > board )
{
    int iBoardSize = board.size () ;
    vector < vector < vector < int > > > vMap ( iBoardSize , ( vector < vector < int > > ( iBoardSize , ( vector < int > ( 2 , 1e6 ) ) ) ) ) ;            // 0 Vertical , 1 Horizontal
    priority_queue < mapInfo , vector < mapInfo > , comp > pqBFS ;
    int irgXDirection [ 4 ] = { -1 , 0 , 1 , 0 } ;
    int irgYDirection [ 4 ] = { 0 , -1 , 0 , 1 } ;



    vMap [ 0 ] [ 0 ] [ 0 ] = vMap [ 0 ] [ 0 ] [ 1 ] = 0 ;
    pqBFS.push ( { 0 , 0 , 0 , 0 } ) ;
    pqBFS.push ( { 0 , 0 , 1 , 0 } ) ;
    while ( ! pqBFS.empty () )
    {
        mapInfo currentInfo = pqBFS.top () ;
        pqBFS.pop () ;

        if ( currentInfo.iCost > vMap [ currentInfo.iX ] [ currentInfo.iY ] [ currentInfo.iDirection ] )
            continue ;

        for ( int i = 0 ; i < 4 ; ++i )
        {
            int iX = currentInfo.iX + irgXDirection [ i ] ;
            int iY = currentInfo.iY + irgYDirection [ i ] ;
            int iDirection = i & 1 ;
            int iCost = ( iDirection == currentInfo.iDirection ) ? 100 : 600 ;
            iCost += currentInfo.iCost ;

            if ( ( -1 == iX ) || ( -1 == iY ) || ( iBoardSize == iX ) || ( iBoardSize == iY ) || ( 1 == board [ iX ] [ iY ] ) )        // Out of bound, find wall
                continue ;
            if ( vMap [ iX ] [ iY ] [ iDirection ] <= iCost )        // Current path is worse
                continue ;

            vMap [ iX ] [ iY ] [ iDirection ] = iCost ;
            pqBFS.push ( { iX , iY , iDirection , iCost } ) ;
        }        
    }


    return std :: min ( vMap [ iBoardSize - 1 ] [ iBoardSize - 1 ] [ 0 ] , vMap [ iBoardSize - 1 ] [ iBoardSize - 1 ] [ 1 ] ) ;
}