Programmers - 경주로 건설 - 포기

---

title: Programmers - 경주로 건설 - 포기
date: 2022-07-24
tags:

• Algorithm
• DP
• DFS
• BFS

---

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

문제 요약

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

문제 풀이

이틀간 이 문제만 계속 시도하였다.
계속하여 정확성 56점에서 실패하며, 테스트 케이스 및 여러 AC 프로그램을 살펴보았으나 도대체 뭐가 문제인지 알아낼 수 없었다.
포기하고 나중에 다시 풀 계획이다.
DFS 시도 - BFS 추가 구현 순으로 문제를 풀었으나, 두가지 모두 동일한 테스트에서 실패한다.

프로그램 using DFS

#include <vector>
#include <algorithm>

#define DOWN    0
#define RIGHT    1
#define UP        2
#define LEFT    3

using std :: vector ;

vector < int > * g_vpBoard ;
vector < vector < vector < int > > > g_vDP ;
int g_iBoardSize ;
int g_iMinCost ;

void getMinimumBuildCost ( int iX , int iY , int iDirection , int iCost )
{
    int iXDirection [ 4 ] = { 1 , 0 , -1 , 0 } ;
    int iYDirection [ 4 ] = { 0 , 1 , 0 , -1 } ;
    int iMinimumCost = 1e5 ;



    if ( ( iX == g_iBoardSize - 1 ) && ( iY == g_iBoardSize - 1 ) )
        g_iMinCost = std :: min ( g_iMinCost , iCost ) ;
    if ( g_iMinCost < iCost )
        return ;

    for ( int i = 0 ; i < 4 ; ++i )
    {
        int iTempX = iX + iXDirection [ i ] ;
        int iTempY = iY + iYDirection [ i ] ;
        int iDirectionCost = ( i == iDirection ) ? 100 : 600 ;

        if ( ( iTempX < 0 ) || ( g_iBoardSize - 1 < iTempX ) || ( iTempY < 0 ) || ( g_iBoardSize - 1 < iTempY )
            || ( 1 == g_vpBoard [ iTempX ] [ iTempY ] ) || ( g_vDP [ iTempX ] [ iTempY ] [ i ] < iCost + iDirectionCost ) )
            continue ;

        g_vDP [ iTempX ] [ iTempY ] [ i ] = iCost + iDirectionCost ;

        getMinimumBuildCost ( iTempX , iTempY , i , iCost + iDirectionCost ) ;
    }
}

int solution ( vector < vector < int > > board )
{
    g_iBoardSize = board.size () ;
    g_vpBoard = board.data () ;
    g_vDP.resize ( g_iBoardSize , ( vector < vector < int > > ( g_iBoardSize , ( vector < int > ( 4 , 1e5 ) ) ) ) ) ;
    g_iMinCost = 1e5 ;

    g_vDP [ 0 ] [ 0 ] [ 0 ] = g_vDP [ 0 ] [ 0 ] [ 1 ] = g_vDP [ 0 ] [ 0 ] [ 2 ] = g_vDP [ 0 ] [ 0 ] [ 3 ] = 0 ;

    getMinimumBuildCost ( 0 , 1 , RIGHT , 100 ) ;
    getMinimumBuildCost ( 1 , 0 , DOWN , 100 ) ;


    return g_iMinCost ;
}

프로그램 using BFS

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

#define UP        0
#define LEFT    1
#define DOWN    2
#define RIGHT    3

using std :: vector ;
using std :: queue ;

struct node
{
    int iX ;
    int iY ;
    int iCost ;
    int iDirection ;

    node ( int iX , int iY , int iCost , int iDirection ) :
        iX ( iX ) , iY ( iY ) , iCost ( iCost ) , iDirection ( iDirection ) {}
} ;

int solution ( vector < vector < int > > board )
{
    vector < int > * vpBoard = board.data () ;
    int iBoardSize = board.size () ;
    vector < vector < vector < int > > > vDP ( iBoardSize , ( vector < vector < int > > ( iBoardSize , ( vector < int > ( 4 , 1e5 ) ) ) ) ) ;
    queue < node > qBFS ;
    int iXDirection [ 4 ] = { -1 , 0 , 1 , 0 } ;
    int iYDirection [ 4 ] = { 0 , -1 , 0 , 1 } ;
    int iAnswer = 1e5 ;
    vector < vector < bool > > vVisit ( iBoardSize , ( vector < bool > ( iBoardSize , false ) ) ) ;



    vDP [ 0 ] [ 0 ] [ 0 ] = vDP [ 0 ] [ 0 ] [ 1 ] = vDP [ 0 ] [ 0 ] [ 2 ] = vDP [ 0 ] [ 0 ] [ 3 ] = 0 ;
    vVisit [ 0 ] [ 0 ] = true ;

    qBFS.emplace ( 0 , 1 , 100 , RIGHT ) ;
    qBFS.emplace ( 1 , 0 , 100 , DOWN ) ;
    while ( ! qBFS.empty () )
    {
        node tempNode = qBFS.front () ;
        qBFS.pop () ;

        if ( vDP [ tempNode.iX ] [ tempNode.iY ] [ tempNode.iDirection ] < tempNode.iCost )
            continue ;

        if ( ( tempNode.iX == iBoardSize - 1 ) && ( tempNode.iY == iBoardSize - 1 ) )
            return iAnswer = std :: min ( iAnswer , tempNode.iCost ) ;

        for ( int i = 0 ; i < 4 ; ++i )
        {
            int iTempX = tempNode.iX + iXDirection [ i ] ;
            int iTempY = tempNode.iY + iYDirection [ i ] ;
            int iDirectionCost = ( i == tempNode.iDirection ) ? 100 : 600 ;

            if ( ( iTempX < 0 ) || ( iBoardSize - 1 < iTempX ) || ( iTempY < 0 ) || ( iBoardSize - 1 < iTempY ) || ( 1 == vpBoard [ iTempX ] [ iTempY ] ) )
                continue ;
            if ( ( vVisit [ iTempX ] [ iTempY ] ) && ( vDP [ iTempX ] [ iTempY ] [ i ] < tempNode.iCost + iDirectionCost ) )
                continue ;

            vDP [ iTempX ] [ iTempY ] [ i ] = tempNode.iCost + iDirectionCost ;
            vVisit [ tempNode.iX ] [ tempNode.iY ] = true ;
            qBFS.emplace ( iTempX , iTempY , tempNode.iCost + iDirectionCost , i ) ;
        }
    }


    return iAnswer;
}