chogahui05   3년 전

2번 쿼리 같은 경우에

2 u v k가 u에서 v까지 가는 경로에 존재하는 정점 중 k번째 정점을 출력한다. 

고 되어 있습니다.

예제 입력을 예로 들어보자면

2 4 6 4의 경우, 4 - 2 - 1 - 3 - 6으로 가므로 4번째 노드는 3이 맞습니다만.

2 4 6 9의 경우, 9번째로 방문하는 노드가 존재하지 않습니다. 프로그램의 처리에 따라서, 런타임 오류가 날 수도 있고요.

아니면 6이라고 해 버릴수도 있겠지요. -1이라고 처리하거나. (코드들 몇 개를 훑어보니 런타임 오류가 날 만한 게 상당히 많이 보입니다.)

그렇기 때문에 k의 조건을 명시해 주는 게 어떨까 합니다.

2 u v k에서 1<=k<=(dist(u,v)+1)입니다. (단, dist(u,v) = 정점 u에서부터 v까지의 거리)

예를 들어서, 예제 인풋에서 2 4 6 k가 들어온 경우, k는 dist(4,6) + 1 = 4 + 1 = 5까지 들어오는 게 맞습니다.

startlink   3년 전

추가했습니다.

chogahui05   3년 전

헉.. k는 u에서 v로 가는 경로의 비용보다 작거나 같다.

를 u에서 v로 가는 거리보다 작거나 같다로 수정해 주셨으면 좋겠습니다아...

경로의 비용하고 거리는 다른 개념인 듯 싶습니다.

(제가 언어 실력이 많이 부족해서 조건이 딱히 떠오르지는 않습니다만.. 경로의 비용이라고 하면 u에서 v까지 가는 데 통과한 간선의 총 cost 합으로 해석이 되어서요.

아마 다르게 봐야 맞지 않을까 싶습니다)

startlink   3년 전

k ≤ 1 u v의 결과 아닌가요? 쿼리 1번을 설명하는데 사용한 표현이라서 그렇게 작성했습니다.

chogahui05   3년 전

5에서 6까지 가는 경로를 예로 들자면

5 (1번째)

2 (2번째)

1 (3번째)

3 (4번째)

6 (5번째)

로 방문합니다.

이것은 5 ~ 6까지 가는 데 드는 경로의 비용인 6과는 다릅니다.

즉, 예제 input에서 2 5 6 k라는 쿼리가 들어오면 k는 5보다 작거나 같아야 합니다. 제가 언어실력이 부족해서 그런 듯 싶습니다... ㅠㅠ

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