[프로그래머스][Level3][C++][DFS] 2020 카카오 인턴십 -경주로 건설 - 컴도리돌이

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

 

1.  문제를 보자마자 DFS와 BFS를 떠올렸고, DFS가 더 자신있기에 DFS로 문제를 풀기로 결심했다.
2.  처음 가볍게 코드를 짰고 주어진 테스트케이스가 운좋게 통과되었지만 제출하는 동시에 50%가 시간초과가 떴다.
3.  처음 코드에서는 단지 board가 벽인 부분을 제외하고 모든 곳을 방문했기에 25 * 25 board에서 모든 길을 탐색했기에 시간 초과가 뜬것으로 예상했다.
4. 이전 코드와 다르게 경로에 대한 비용을 미리 저장시켜놓았다.
5. 상하좌우로 해당 board로 이동했지만 해당 경로가 이미 값이 있고 그에 대한 비용보다 작다면 return을 시켜놓았다.
6. 하지만 14번 테스트케이스에서 오류가 났다. 물론 탐색하는 방향을 "상우하좌" 로 바꿔서 맞긴 했지만 해당 문제를 제대로 풀기 위해서는 3차원 배열로 해결을 해야한다. ex . weigh[n][n][4]  여기서 4에 해당한 값은 상하좌우를 의미한다.  

#include <string>
#include <vector>
#include <queue>

using namespace std;

const int dx[] ={0,1,0,-1};
const int dy[] ={1,0,-1,0};
int answer = INT32_MAX;
void dfs(vector<vector<int>>& board,vector<vector<bool>>& visited,vector<vector<int>>& weight,int x ,int y,int same,int cost)
{
    if(cost>weight[x][y]) return; //이미 해당 경로가 cost값보다 작으면 return <- 시간초과 해결
    if(cost < weight[x][y]) weight[x][y] = cost; //cost가 해당 경로 값보다 작으면 해당 경로의 값을 cost를 저장
    if(x == board.size()-1 and y == board.size()-1) //끝지점에 도착했으면 answer 값과 계속 비교하고 return
    {
        answer = answer < cost ? answer : cost;
        return;
    }
    for(int i=0; i<4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 and ny >=0 and nx < board.size() and ny < board.size() and !board[nx][ny] and !visited[nx][ny])
        {
            visited[nx][ny] = true; 
            // 같은 방향이면 same = i 일 경우 cost는 +100
            if(same == i or (x ==0 and y ==0)) dfs(board,visited,weight,nx,ny,i,cost+100);
            // 그렇지 않을 경우 cost는 100 + 500  
            else dfs(board,visited,weight,nx,ny,i,cost+600);
            // 다시 경로 방문 해제
            visited[nx][ny] = false;
        }
    }
}

int solution(vector<vector<int>> board) {
    vector<vector<bool>> visited(board.size(),vector<bool>(board.size(),false));
    vector<vector<int>> weight(board.size(),vector<int>(board.size(),INT32_MAX));
    visited[0][0] = true;
    dfs(board,visited,weight,0,0,0,0);
    return answer;
}