[프로그래머스] 경주로건설

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

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

그냥 적당히 풀었을때는 시간초과가 났었다.

왜지? 하고 알아보니까

(x,y) 좌표로 진행할때, 왼쪽에서 왔을때의 비용(x,y-1)이랑 위쪽에서 왔을때(x-1,y)의 비용이랑 비교해서 더 작은 비용으로 진행한 경로만 계속 진행해줘야 시간초과가 나지 않는다고 한다.

음.. 생각해보니 그렇네 중간에 비교했을때는 A경로가 더 작은 비용이들었는데 나중에는 B 경로가 더 작은 비용이 들게된다는 경우는 최대한 한쪽방향으로 쭉 진행하는 DFS의 특징상 있을 수 없는 일이군!

 

#include <string>
#include <vector>

using namespace std;
int answer;
vector<vector<int>> m_board;
int N=0;
int visited[26][26][4];
int dx[]={0,1,0,-1}; // -> , 아래, 
int dy[]={1,0,-1,0};
void dfs(int x, int y, int cost, int d ) {
    if(x==N-1 && y==N-1) {
        if(cost < answer) answer = cost;
        return;
    }
    if( cost >= answer) return;
    visited[x][y][d]=cost;
    for (int i=0; i<4; i++) {
        int nx = x+dx[i];
        int ny= y+dy[i];
        if(nx<0 || ny <0 || nx>=N || ny>=N || m_board[nx][ny]==1) continue;
        int curCost = 0;
        if(i==d || (x==0&&y==0&& i==1)) {
            curCost = 100;
        }
        else {
            curCost = 600;
        }

        if(cost+curCost < visited[nx][ny][i]){
            dfs(nx, ny, cost+curCost, i);
        } 



    }
}
int solution(vector<vector<int>> board) {
    answer = 987654321;
    N = board.size();
    m_board = board;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N;j++){
            for (int k=0; k<4; k++) {
                visited[i][j][k]=987654321;
            }
        }
    }
    dfs(0,0,0,0);
    return answer;
}