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

오늘 푼 문제

 

4. 경주로 건설 / Lv.3 / 시간 : 89분(시간초과)

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

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

 

1. 틀린 코드

코너인지 직진로인지 계산을 처음에는 다음과 같이 구했다.

1) queue 형태의 배열(list)에서 가장 선두의 값을 추출한다(cur)

1) cur을 기준으로 상하좌우로 갈 수 있는 길을 먼저 탐색한다.

2) cur에는 직전의 값이 저장되어있으므로(prev) 상하좌우 값을 cur에 저장된 prev의 좌표와 비교해 새로운 가격에(newP)코너 이동일 경우 600원을, 같은 방향으로 이동할 경우 100원을 추가한다.

3) 초기값은 Infinity로 세팅되어있는 비용을 저장하는 2차원 배열에(visited) 저장되어있는 기존의 비용과 newP를 비교해 더 작거나 같은 경우 그 비용을 업데이트해주고 list에 추가한다.

 

코드는 날려버리는 바람에 없지만 이 때 최대 점수가 69.2?를 넘지 못했다.. 올클이 안됐음. 

 

 

2. 이전 값이 아니라 방향저장으로 바꿔서 풀었다.

function solution(board) {
    var answer = 0;
    let n = board.length;
    let visited = Array.from(board,()=>new Array(n).fill(Infinity));
    let [x,y] = [0,0];
    let list = [[x,y,0,4]]; // x,y,price,direction
    let directions = [[0,1],[1,0],[0,-1],[-1,0]];
    while(list.length){
        let [i,j,price,d] = list.shift();
        directions.forEach((arr,index)=>{
            if(Math.abs(d-index)!==2){
                let [newX,newY] = [i+arr[0],j+arr[1]];
                if(board[newX] && board[newX][newY]===0){
                    let newP = price+((!(d-index)||d===4)?100:600);
                    if(visited[newX][newY]>=newP){
                        visited[newX][newY] = newP;
                        list.push([newX,newY,newP,index])
                    }
                }
            }
        })
    }    
    answer = visited[n-1][n-1];
    
    return answer;
}

 

올테케 통과~