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

 

Lv3 . 프로그래머스 경주로 건설 (2020 카카오 인턴십)

 

문제 설명

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

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

 

그렇게 어려운 문제가 아닌데도 꽤 오랜 시간이 필요했던 문제였다. bfs는 이제 어느정도 할 줄 안다고 자신감을 갖고 있었는데 겸손해야겠다... . .  

 

1. 처음엔 dfs로 재귀를 돌면서 모두 체크했더니 당연히 시간초과가 났다. 

2. 재귀함수를 구현해서 memoization을 해주면서 dp로 풀어볼까 해서 접근했더니 테스트 케이스 부터 제대로 나오지 않았다.

 

3. 결론적으로는 bfs + dp 로 문제를 해결했다. 

 

내가 삽질했던 두 가지 포인트가 있다. 

 

1) visit 배열 선언 후 방문한 노드를 체크했다. visit[25][25][4] 를 선언한 다음, 네 방향에서 방문 여부를 체크하고, 방문했다면 다시 방문하지 못하게 했다. 이렇게 하면 틀릴 수 밖에 없다. 한 지점에 제일 처음 도착한 경로가 최소 비용이라는 확신을 할 수 없다. 뒤늦게 오는 다른 경로가 그 전 경로보다 비용이 적을 수 도 있다. 방문 여부를 체크할 필요 없이, dp 배열에 값을 비교하면서, 더 적은 비용이 들면 갱신하고, 다시 queue에 push하여 탐색을 계속 한다.

2) dp를 3차원 배열로 해서 비용을 저장해야 한다. 한 지점으로 올 수 있는 방향은 4가지 이다. 현재 비교했을 때 더 작은 값이더라도, 뒤에 가서 코너 비용이 더 들 수도 있다는 것을 고려해야 한다. 그렇기 때문에 4가지 방향 따로 저장해줘야 한다. (dp[i][j][k] : (i,j)까지 k 방향으로 오는데 드는 비용)

 

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,1,-1};
int dp[26][26][5];
int row, col;

struct info{
    int x; int y; int dir;
    void setinfo(int dx, int dy,int dd){
        x = dx ; y = dy; dir = dd;
    }
};
int range(int x, int y){
    if(x>=0 && y>=0 && x<row && y<col) return 1;
    return 0;
}
void init(){
    for(int i=0;i<row;i++)
        for(int j=0;j<col;j++)
            for(int k=0;k<4;k++)
                dp[i][j][k] = INT_MAX;
}
int solution(vector<vector<int>> board) {
    row = board.size();
    col = board[0].size();
    init();
    
    queue <info> q;
    info i;
    i.setinfo(0,0,-1);
    q.push(i);
    dp[0][0][0] = 0;
    dp[0][0][1] = 0;
    dp[0][0][2] = 0;
    dp[0][0][3] = 0;
    
    int ans = INT_MAX;
    while(!q.empty()){
        auto e = q.front();
        q.pop();
        
        if(e.x == row -1 && e.y == col -1){
            continue;
        }
        
        for(int i=0;i<4;i++){
            int nx = e.x + dx[i];
            int ny = e.y + dy[i];
            if(range(nx, ny) && board[nx][ny]!= 1){
                info n;
                if(e.dir == -1){ //시작 바로다음일때
                    dp[nx][ny][i] = min(dp[nx][ny][i] , 100);
                    n.setinfo(nx, ny, i);
                    q.push(n);
                }
                else if(e.dir != i){
                    if(dp[nx][ny][i] > dp[e.x][e.y][e.dir] + 600){ //코너
                        n.setinfo(nx, ny, i);
                        q.push(n);
                        dp[nx][ny][i] = dp[e.x][e.y][e.dir] + 600;
                    }
                }
                else if(e.dir == i){
                    if(dp[nx][ny][i] > dp[e.x][e.y][e.dir] + 100){
                        n.setinfo(nx, ny, i);
                        q.push(n);
                        dp[nx][ny][i] = dp[e.x][e.y][e.dir] + 100;
                    }
                }
            }
        }
    }      
    for(int i=0;i<4;i++)
        ans = min(ans, dp[row-1][col-1][i]);
    return ans;
}