jng6017   1년 전

최소한의 연료 소비량으로 시작지점에서 도착지점에 가고 싶어한다.

사용하는 차량들이 소비하는 연료의 양을 측정할 떄는 다음과 같은 방법을 사용한다.

지역마다 높이가 주어지고 이동 할 칸의 높이에 따라 다음과 같이 연료 소비량이 주어진다. (반드시 상하좌우로만 움직일 수 있다.)

현재 위치의 높이 < 이동할 곳의 높이 --> (이동할 곳의 높이 - 현재 높이)^2

현재 높이 = 이동 높이 --> 1

현재 높이 > 이동 높이 -> 현재 높이 - 이동 높이

정사각형으로 된 칸으로 이루어 져있으며 출발지점과 도착 지점이 주어질떄 최소의 연료만을 소비하여 갈 때 최소 연료 소비량을 구하여라.

지도 가로 세로 크기 1<n(가로),m(세로)<1000가 주어진다.

m줄에는 n개씩 지역 높이가 주어진 후 출발지점과 도착지점이 주어진다.


//////////////////////////////////////////////////////////

상하좌우를 간선이라 생각하고 시작점에서 다익스트라로 최단경로찾기 하듯이 풀었는데

최소값 찾는거는 다 보고 찾으면 n^2이라서 인덱스트리로 짯습니다. 1000,1000 넣으면 시간초과 나는데 도와주세요

ex)

3 3

5 7 8

10 10 13

12 13 15

1 1

3 2

//////

22




p.s 혹시 다익스트라 응용 문제 있으면 추천 좀 해주세요 ㅎㅎ

appa   1년 전

pow함수를 써서 느린 것 같네요. 그냥 곱셈으로만 바꾸어도 많이 빨라질 겁니다. 전 다익스트라를 짤 때, 간선의 정보(어디에 도착하는 간선인지, 누적합이 얼마인지. 정렬은 누적합 순으로)를 우선순위 큐(priority_queue)에 담아 사용하면 편하더라구요.

다익스트라를 이용해 풀 수 있는 문제로는 아래 문제들이 있습니다.

https://www.acmicpc.net/problem/2325

https://www.acmicpc.net/problem/10217

https://www.acmicpc.net/problem/1504

https://www.acmicpc.net/problem/1753

https://www.acmicpc.net/problem/5719

jng6017   1년 전

inline이 안에 있는거는 main안에 들어 있는거 처럼 행동되서 차이가 없다고 하던데 아닌가요?

우선순위 큐 사용 할떄 힙으로 짤때

a->b로 갔을때 b의 누적합을 넣은 상태에서 a->c->b의 누적합이 더 작아 넣을려고 할때 힙 어딘가에 있을 b에 대한 처음 누적합과 값이 중복되는건 어떻게 처리하나요?

appa   1년 전

다익스트라 알고리즘의 원리를 살펴보시면, 해 집합 S의 크기를 하나씩 늘려간다고 할 수 있습니다.

S의 두 정점인 a, b에 대해 a에서 b로 가는 경로가 있다면 최단거리임이 명백한 것이지요. 따라서 a->b로 갔을 때 b의 누적합보다 a->c->b가 더 작으려면, 애초에 a->c를 간 다음에 c->b를 가게 됩니다. 그렇더라도 경우에 따라 집합 S의 크기가 한 번에 1보다 큰 정수씩 증가하는 경우에는 말씀하신 상황처럼 우선순위 큐에서 pop한 것이 현재에 이르는 정점까지의 최단거리보다 더 클 수가 있는데, 그럴 때에는 별도로 배열을 선언하셔서 해당 지점까지 도착하는데 필요한 최단 거리를 저장해주시면 됩니다.

의사코드를 작성하면 다음과 같습니다.

시작 지점 : s , 도착 지점 : e

d(i) : i번째 지점에 이르는 최단 거리(처음엔 모두 최댓값으로 초기화되어있음)

priority_queue : Q


d(s) = 0을 해주고 s에 연결된 간선을 모두 Q에 넣어준다.

while (Q에 원소가 있을 동안) {

Q에서 가장 앞에 있는 원소를 뺌. 그 원소를 x라 하자.

d(x의 도착지점)보다 x가 가진 가중치가 더 안 좋으면 : continue;(while문 시작으로 되돌아감)

x랑 연결된 간선들 중 d(x에서 뻗어나가는 간선의 도착점)이 갱신되는 것들에 한해서 d를 갱신하고, Q에 해당 간선을 넣어줌.

}

이렇게 되는 것 같습니다.

appa   1년 전

여담으로 질문하신 문제 링크를 남겨주실 수 있으신가요?

jng6017   1년 전

이게 학원사이트 문제라서요 ㅋㅋㅋㅋ 로그인을 안하면 볼수 가 없는.... 복사도 안되고 ㅠㅠ......

jng6017   1년 전

필요하시면 채점 데이터랑 문제 알집으로 보내드릴까요?

jng6017   1년 전

우선순위 큐가 최솟값을 lgN만에 찾아서 사용 하는 건가요? 만약 그렇다면 전 인덱스트리를 사용하였는데 인덱스트리는 lgN이 아닌가요?

appa   1년 전

둘 다 log N만에 찾는 것이 맞습니다. 누구에게나 공개된 문제가 아니기 때문에 따로 받지는 않겠습니다.

jng6017   1년 전

질문에 답해 주셔서 감사합니다.

baekjoon   1년 전

이거 비슷한 문제 이 사이트에도 아마 있을걸요? 본 기억이 나네요

댓글을 작성하려면 로그인해야 합니다.