코딩테스트 -- 경주로 건설 - (프로그래머스 / C++)

프로그래머스

 

문제!

 

---

 

건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다.
제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다.
설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다.
경주로의 출발점은 (0, 0) 칸(좌측 상단)이며, 도착점은 (N-1, N-1) 칸(우측 하단)입니다. 죠르디는 출발점인 (0, 0) 칸에서 출발한 자동차가 도착점인 (N-1, N-1) 칸까지 무사히 도달할 수 있게 중간에 끊기지 않도록 경주로를 건설해야 합니다.
경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있으며, 벽이 있는 칸에는 경주로를 건설할 수 없습니다.
이때, 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로 라고 합니다.
또한 두 직선 도로가 서로 직각으로 만나는 지점을 코너 라고 부릅니다.
건설 비용을 계산해 보니 직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 추가로 듭니다.
죠르디는 견적서 작성을 위해 경주로를 건설하는 데 필요한 최소 비용을 계산해야 합니다.

예를 들어, 아래 그림은 직선 도로 6개와 코너 4개로 구성된 임의의 경주로 예시이며, 건설 비용은 6 x 100 + 4 x 500 = 2600원 입니다.

 

---

요약하면 경주로 건설시에 커브면은 +500 직선도로는 +100의 비용이 드는데 출발지인 0,0 에서  목적지인 m-1,n-1 까지의 최소 건설비용을 구하는 문제!

 

제가보기엔... 탐색문제 + 커브를 구하기위한 생각? 이면 충분히 풀수있을것 같습니다!

 

1. 일반적인 이동탐색  -- 상하좌우로 이동할수있는지 판단하여 이동시켜 목적지까지 도달하는지!

2. 커브는 보통 방향이 바뀔때 생성되는데!

변수명 하나로 현재이동변수와 다음으로 이동될 변수가 같은지 다른지 확인만 해주면 될 것 !

 

 

같았는데..... 시간초과 나네요 ㅋㅋㅋ (실패는 안뜨는거보니 방법은 맞는거같기도..?)

#include <string>
#include <vector>

#include <iostream>
using namespace std;

int allpay=987654321;

void find(vector<vector<int>> board,int a,int b,int count,int check){
    if(a==board.size()-1 and b==board[0].size()-1){
        allpay=min(allpay,count);
    }
    else{
        if(a!=0){//위
            if(board[a-1][b]!=1){
                board[a][b]=1;
                if(check==1 or check==0){
                    find(board,a-1,b,count+100,1);
                }
                else{
                    find(board,a-1,b,count+600,1);
                }
                board[a][b]=0;
            }
        }
        if(b!=0){//왼
            if(board[a][b-1]!=1){
                board[a][b]=1;
                if(check==2 or check==0){
                    find(board,a,b-1,count+100,2);
                }
                else{
                    find(board,a,b-1,count+600,2);
                }
                board[a][b]=0;
            }
        }
        if(a<board.size()-1){//아래
            if(board[a+1][b]!=1){
                board[a][b]=1;
                if(check==3 or check==0){
                    find(board,a+1,b,count+100,3);
                }
                else{
                    find(board,a+1,b,count+600,3);
                }
                board[a][b]=0;
            }
        }
        if(b<board[0].size()-1){//우
            if(board[a][b+1]!=1){
                board[a][b]=1;
                if(check==4 or check==0){
                    find(board,a,b+1,count+100,4);
                }
                else{
                    find(board,a,b+1,count+600,4);
                }
                board[a][b]=0;
            }
        }
    }
    
}

int solution(vector<vector<int>> board) {
    int answer = 0;
    
    find(board,0,0,0,0);
    
    return allpay;
}

단순히 상하좌우를 모두살피고 커브변수 check를 통해 걸러냈는데

재귀를 통해 모든 부분을 살피는데 초과나는것 같기도....하네요

 

 

다른방법을 찾아보다  재귀함수안에 현재 최솟값보다 커지는순간 그만돌아가도록 아래코드를 추가해주니...!

if(allpay<=count){
        return;
    }

정확성 52 >> 72 오르긴했지만 여전히 시간초과 나는 케이스가 있네요..

 

 

 

 

다시 시작!

 

현재 코드에서 추가만 하겠습니다.

int dp[26][26]={0};
dp[0][0]=0; 출발지

이렇게 값을 저장할 배열선언!

 

 

 

그리고 재귀함수 안에 아래처럼 추가하면!!

if(dp[a][b]==0 or dp[a][b]>=count){
        dp[a][b]=count;
    }
    else{
        return;
    }

이번엔 실패가... ㅋㅋㅋ

 

여기서 먼가 바꾸어보다가 현재 함수안에있는 if문의 순서를 바꾸었을때 값이 변경된다는 것을 알게되었습니다....

(세상에나;;  현재 상좌하우 >> 우상하좌 (정확성 100퍼;;))

이에대한 설명을 좀 찾아보니 방향에따라 추가되는 값이 변경되기에 순서에따라 값이 바뀔수도 있다네요..?

 

이부분은 추후에 좀더 보완해보겠습니다... 답이.. 이상하네요

 

 

저의 답

#include <string>
#include <vector>

#include <iostream>
using namespace std;

int allpay=987654321;
int dp[26][26]={0};

void find(vector<vector<int>> board,int a,int b,int count,int check){
    if(dp[a][b]==0 or dp[a][b]>=count){
        dp[a][b]=count;
    }
    else{
        return;
    }
    if(b<board[0].size()-1){//우
        if(board[a][b+1]!=1){
            board[a][b]=1;
            if(check==4 or check==0){
                find(board,a,b+1,count+100,4);
            }
            else{
                find(board,a,b+1,count+600,4);
            }
            board[a][b]=0;
        }
    }
    if(a!=0){//위
        if(board[a-1][b]!=1){
            board[a][b]=1;
            if(check==1 or check==0){
                find(board,a-1,b,count+100,1);
            }
            else{
                find(board,a-1,b,count+600,1);
            }
            board[a][b]=0;
        }
    }
    if(a<board.size()-1){//아래
        if(board[a+1][b]!=1){
            board[a][b]=1;
            if(check==3 or check==0){
                find(board,a+1,b,count+100,3);
            }
            else{
                find(board,a+1,b,count+600,3);
            }
            board[a][b]=0;
        }
    }

    if(b!=0){//왼
        if(board[a][b-1]!=1){
            board[a][b]=1;
            if(check==2 or check==0){
                find(board,a,b-1,count+100,2);
            }
            else{
                find(board,a,b-1,count+600,2);
            }
            board[a][b]=0;
        }
    }





}

int solution(vector<vector<int>> board) {
    int answer = 0;
    dp[0][0]=0;
    find(board,0,0,0,0);

    // for(int i=0;i<26;i++){
    //     for(int j=0;j<26;j++){
    //         cout<<dp[i][j]<<",";
    //     }   
    //     cout<<endl;
    // }

    return dp[board.size()-1][board[0].size()-1];
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!