알고리즘95 :: 다익스트라 로직

다익스트라를 적용할 때 맵에 값을 갱신할 필요가 있을 경우

상황은 다음과 같이 가정합니다.

맵이 존재하고 시작 위치에서 출발했을때 방향은 무관 

각 맵마다 (점수,시간) 이 주어지고 한칸 움직일때마다 1초가 지난다고 가정

이럴 경우에 최대 점수는? 단, 방문했던 맵은 다시 방문가능 하지만 점수는 획득 불가, 시간이 초과한곳도 마찬가지로 점수 획득 불가.

 

코드 컨셉 : 백트래킹

최대 맵의 크기 : N 이라고 한다면 

재귀함수 부분만 구성해보면

if(time>N){	
         answer = Math.max(answer,maxAnswer);
		 return;
}
		
		for(int i=0; i<4; i++){
            int ddx = x + dx[i];
            int ddy = y + dy[i];
            if(ddx<0 || ddx>=r || ddy<0 || ddy>=r) continue;
            int delivery_x = ddx*r + ddy;
         
                if(delivery[delivery_x][0]>time && visit[ddx][ddy]== 0){
                    visit[ddx][ddy] = 1;
                    answer += delivery[delivery_x][0];
                    DFS(ddx,ddy,time+1,delivery,r);
                    abswer -= delivery[delivery_x][0];
                }else{
                    DFS(ddx,ddy,time+1,delivery,r);
                }
            };
        }
	}