[프로그래머스] 경주로 건설 2020 카카오 인턴쉽 level3

문제 :

programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

 

분석 :

이 문제는 백준에서 풀었던 내리막길 문제와 비슷하게 dp + dfs의 조합문제였다.

우선 미리 고하지만 TC 24번만 통과하지 못했다 ㅜ

1520번: 내리막 길

다만 상하, 좌우를 이동할때 비용이 달리 들었는데 이 점에서 어떻게 해결하면 좋을지 몰라 하드코딩 하는데 시간을 쩔쩔맸다.

그러던 중 다른 분의 아이디어를 참고해 아 이렇게 접근하는 좋은 방법이 ..! 를 발견했다.

 

1. 값 비용 계산하기(직선 도로, 코너 도로 ?)

직선 도로, 코너 도로 비용 

상하좌우를 돌기 위해 bfs시

int dx[] = { 0, 0, 1, -1 }; //up down left right
int dy[] = { 1, -1, 0, 0 };

의 인덱스를 참고해 돌 것이다. 

 

인덱스 i가 

 

상하일땐 0, 1

좌우일땐 3, 2

 

코너 도로는 상하 -> 좌우 또는 좌우 -> 상하로 즉 인덱스가 0, 1 -> 2, 3으로 또는 2, 3 -> 0, 1로 변화할때 돌고 + 직선 도로 = 600 원의 비용이 돌 것이다. 

 처음 bfs를 돌 시 비용은 -1로 초기화 해주었다. 

그리고 before과 now 인덱스의 값 변화를 비교해 적절한 비용을 계산해 준다 ..! 

 

2. DP 최소 비용 

계산된 비용에 대해

dp [x][y]: (x, y)까지 도로 건설하는데 드는 최소 비용

을 최소 비용이 있으면 갱신시켜주고 다음 방문을 재귀로 이동한다.

 

이때 또 주의해야 할점은 visit를 통해 방문한 장소는 가지 않게 하는 것인데 bfs가 끝나면 돌아오는 과정에서 visit를 false로 만들어 

 다음 for문을 돌고 그에 대한 더 최적의 값이 있다면 dp에 최소의 값으로 다시 계산되어 저장되게 하는 점을 간과해선 안된다.

 

 

c++ 코드 :

//
//  [KAKAO] 2020_trackBuild.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/05/07.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string.h>
#include <queue>

using namespace std;
int nextPay = 0;

//
//vector<vector<int>> board = {{0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,0},{0,0,0,0,1,0,0,0},{0,0,0,1,0,0,0,1},{0,0,1,0,0,0,1,0},{0,1,0,0,0,1,0,0},{1,0,0,0,0,0,0,0}};
vector<vector<int>> board = {{0,0,1},{1,0,1},{1,0,0}};
int size = (int) board.size();
bool visit[26][26];
int dp[26][26];
int answer = 0;

int dx[] = { 0, 0, 1, -1 }; //up down left right
int dy[] = { 1, -1, 0, 0 };

//dp 배열 확인용
void print_dp(){
    for(int i =0; i < board.size(); i++){
        for(int j = 0; j < board.size(); j++){
            cout << dp[i][j] << " ";
        }
        cout << '\n';
    }
    cout << '\n';
}

int calculate_pay(int before, int now){
    if(before == -1){
        return 100;
    }else if((before == 2|| before == 3) &&(now == 0|| now == 1)){
        return 600;
    }else if((before == 0|| before == 1) &&(now == 2|| now == 3)){
        return 600;
    }
    return 100;
}

void make_bfs(int x, int y, int dir, int pay){
    for(int i = 0; i < 4 ; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0|| nx >= size || ny >= size) continue;
        if(board[nx][ny] == 1 || visit[nx][ny] == true) continue;
        
        pay = calculate_pay(dir, i);
        if(dp[nx][ny] < dp[x][y] + pay){
            continue;
        }
        dp[nx][ny] = dp[x][y] + pay;
        visit[nx][ny] = true;
        make_bfs(nx, ny, i, pay);
        //print_dp();
        visit[nx][ny] = false;
        // false가 되고 돌아오는 과정에서 다음 for문을 돌고 그에 대한 더 최적의 값이 있다면 dp에 최소의 값으로 다시 계산되어 저장된다.
        
    }
}


int main(){
    
    // 초기화
    memset(visit, false, sizeof(visit));
    for(int i =0; i < board.size(); i++){
        for(int j = 0; j < board.size(); j++){
            dp[i][j] = 10000000;
        }
    }
    
    dp[0][0] = 0;
    make_bfs(0, 0, -1, 0);
    
    cout << dp[size -1][size -1] << '\n';
    
   
    return 0;
}

 

결과 :

뭘 빼먹은 것일까나 .. 아직은 잘 모르겠다 ㅠ 

알려주시면 감사하겠습니다 .. 🥺🥺