[C/C++] Lv3 프로그래머스 - 경주로 건설

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

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

- 접근법

N(맵의 크기)이 25이므로 처음에 생각나는 풀이는 완전탐색 DFS 이다.

하지만 최단거리를 찾는 문제가 아닌, 트랙을 설치하는 최소비용을 찾는 것이고 최대한 커브길을 적게만들면서 도착지점으로 오는 것이 목표이기때문에, 각 위치에서 동서남북을 모두 탐색해야만 한다.

따라서 아무런 조건 장치 없이 모든 경우를 돌려버리면 시간초과가 나고 말것이다.

 

그렇다면 DFS를 효율적으로 돌릴 수 있는 방법을 모색해야한다.

결국 문제가 요구하는 것은 최대한 직진도로를 많이 만들고 커브트랙을 적게 만들면서 도착지점에 도착하게 만들어야 답을 얻을 수 있다. 즉, 내가 (0,0)에서 트랙을 건설하기 시작해서 임의의 (x,y) 좌표에 도달했을때 만들어진 트랙들의 비용도 최소화해야한다.

즉, 이 말을 정리하면 다음과 같다.

(0,0)에서 (N-1,N-1) 까지 트랙비용 최소화

(0,0)에서 (x,y) 까지 트랙비용 최소화

 

어디서 많이 본 개념이다.

바로 DP를 DFS에 이용하는 것이다.

즉 Dy[x][y] = (0,0)에서 (x,y)까지 경주로를 건설하면서 얻은 가장 최소비용 을 이용하면 빠른 시간에 답을 얻을 수 있다.

 

 

 

 

---

- 소스코드

#include <string>
#include <vector>
#include <iostream>
#define MINI(A,B) A>B ? B : A
#define INF 99999999
using namespace std;
int N;
int p_x[4]={0,0,1,-1};
int p_y[4]={1,-1,0,0};
bool visit[26][26];
int dist[26][26];
int answer=INF;
void DFS(int x,int y,int r_case,int cost) {
    if(dist[x][y]!=INF && dist[x][y]<cost) { // (x,y)에 설치할 수 있는 트랙의 비용이 기존보다 더 높으면 가지치기
        return;
    }
    dist[x][y]=MINI(dist[x][y],cost);
    if(cost>=answer) return;
    // r_case : 1 좌->우 / 2 우->좌 / 3 위->아래 / 4 아래->위 / 5 출발점
    if(x==N-1 && y==N-1) {
        answer=MINI(answer,cost);
        return;
    }
    int next_x,next_y;
    for(int i=0;i<4;i++) {
        next_x=x+p_x[i];
        next_y=y+p_y[i];
        if(next_x<0 || next_x==N || next_y<0 || next_y==N) continue;
        if(visit[next_x][next_y]) continue;
        if(r_case!=i+1 && r_case!=5) { // 커브를 만들어낸다면
            visit[next_x][next_y]=true;
            DFS(next_x,next_y,i+1,cost+600);
            visit[next_x][next_y]=false;
        }
        else {
            visit[next_x][next_y]=true;
            DFS(next_x,next_y,i+1,cost+100);
            visit[next_x][next_y]=false;
        }
    }
}
int solution(vector<vector<int>> board) {
    N=board.size();
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            dist[i][j]=INF;
            if(board[i][j]==1) visit[i][j]=true;
        }
    }
    visit[0][0]=true;
    DFS(0,0,5,0);
    return answer;
}