쿠팡 작년 CATCH test 풀면서 생각하는건데


다음과 같이 있을 때 "쿠팡본사"에서 어느 지역을 갈 때 최소 weight를 구해야 하는데 재귀로밖에 못풀겠어요


vertex를 edge로 타고 들어갈 때 weight값을 계속 더해 나가면서 더 작은 값으로 업데이트 할 수 있으면 할려고 하거든요 하나의 재귀 함수로 weight값 들고 들어가서 구현하기 했는데


재귀 안좋다는 말을 하도 들어서 다른 방법이 있나 싶네요


이를테면 저의 구현은 아래와 같습니다 언어는 JAVA입니다


초기값은 dijkstra(graph, ds, "쿠팡본사", 0);


/* 파라미터 : 그래프 자료구조 graph, 최소값 세팅 자료구조 ds, 하나의 Vertex ds, weight 더한 값 sumLen */

public static void dijkstra(HashMap<String, Node> graph, ArrayList<DijkDs> ds, Node node, float sumLen) {

for(int i = 0; i < node.linkedInfo.size(); i++) {    // Vertex에 연결된 놈들 수 만큼

for(int j = 0; j < ds.size(); j++) {    // 최소weight 자료구조와

if(ds.get(j).destNode.equals(node.linkedInfo.get(i).linkedV) // 일치하는 놈 중

&& (ds.get(j).len > sumLen + node.linkedInfo.get(i).len)) { // len 업데이트로 더 작아질 수 있는 경우

ds.get(j).len = sumLen + node.linkedInfo.get(i).len; // 최소값으로 세팅

ds.get(j).depNode = node.vertex;    // 현재 Vertex

dijkstra(graph, ds, graph.get(node.linkedInfo.get(i).linkedV), ds.get(j).len);    // 재귀

}

}

}

}