최단경로에 관한 질문입니다.

  • lionix
    lionix

    현재 온라인 Judge에서 문제를 하나 보고 있는데

    어떤 방식으로 접근해야할지 잘 몰라서 질문드립니다!

    1 2 3 4 5

    5 4 3 2 1

    0 9 8 7 1

    9 4 7 5 8

    2 3 4 9 3

    이정도의 각각의 어레이 내용에 비용이 있습니다.

    맨 위 1,1 부터 끝점 5,5 까지의 최소합을 구하려면..

    다이나믹을 이용하여 우아하게 구현이 가능하지만..

    제가 원하는 좌표 x1,y1 -> x2, y2까지의 최소 비용을 구하려면

    어떤 알고리즘으로 접근해야하는지 궁금합니다.

    BFS(너비우선탐색)이나 다익스트라, 플로이드 알고리즘 등 여러개가 있는데

    어레이의 크기가 100 by 100 정도만 되도 인접행렬에 관한 메모리 문제로

    골치가 아프네요. 좋은 방법 있으면 조언 부탁드립니다. ^^


    8년 전
3개의 댓글이 있습니다.
  • Being
    Being

    문제를 좀 더 엄밀히 설명해 주시기 바랍니다. 이동은 어떻게 이루어지며 비용은 무엇을 의미하는지요?


    8년 전 link
  • amok
    amok

    제가 질문을 잘 이해했는지 확신이 없는 상태로 그냥 적당히 답변하겠습니다. 동적 계획법을 언급하진 걸 보면 어레이에서는 아래 혹은 오른쪽 방향으로만 이동이 가능한 문제인 것 같습니다. 원하는 좌표 x1,y1 -> x2, y2까지의 최소 비용을 구하려면 (x1,y1)을 한 꼭지점, (x2,y2)를 그 대각선 방향 꼭지점으로 하는 직사각형에 속하는 좌표들만 남겨두시고 다 없애버리신 후 문제를 풀면 됩니다.


    8년 전 link
  • JongMan
    JongMan

    2차원 배열 위에서 움직인다고 하면 인접 행렬이나 인접 리스트를 직접 만드실 필요가 없습니다. 좌표 (x, y)를 나타내는 각 정점을 만드는 대신, 각 정점을 그냥 좌표로 표현하면 됩니다. 이 때 그래프 구조는 코드에 직접 나타나지 않습니다. 이런 것을 암시적 (혹은 내재적?) 그래프 표현이라고 부릅니다.


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.