인프런 커뮤니티 질문&답변
작성한 질문수
8-R 질문있습니다 :)
해결된 질문
작성
·
48
0
안녕하세요 선생님 🙂
공식만 이해하면 최단거리 알고리즘문제를 맞추는 것은 정말 쉬운 것 같습니다.
아래는 선생님의 강의를 듣기 전에 먼저 풀이해본 코드인데요, 시간복잡도 부분에서 선생님과 큰 차이가 있습니다.
선생님께서는 하나의 함수로 모듈화하여 풀이해주셨는데요, (1. 왔다), (2.갔다)가 하나의 모듈로 재사용될 수 있다는 것이 이해가 되지 않습니다.
1~N번 마을에 있는 학생들은 전부 X번 마을로 갑니다.
X번 마을에 도착한 학생들은 다시 각자의 마을로 돌아갑니다.
위의 2가지 조건 중, 선생님의 풀이로 2번은 이해가 되는데요, 1번이 이해가 되지 않습니다.
선생님께서 말씀해주신대로, 1번 조건을 보면 최단거리를 시작하는 시작점이 없기 때문에 플로이드 와샬이 떠올랐습니다. 이 풀이를 다익스트라로 실현시키기 위해서는 1부터 N까지 for문을 돌려서 하나씩 다익스트라를 돌려주는 방법 밖에 없다고 생각했습니다.
위의 로직이 어떻게 선생님처럼 간단하게 구현이 되는지 알려주시면 감사하겠습니다!
답변 2
0
안녕하세요 유태님 ㅎㅎ
하나의 함수로 모듈화하여 풀이해주셨는데요
->
dijkstra(dist, adj);
dijkstra(dist2, adj2);일단 하나의 함수로 되는 것은 간선 2개를 만들어서 다른 간선을 넘겨서 수행하기 때문에 모듈화가 되는 것인데요.
1~N번 마을에 있는 학생들은 전부 X번 마을로 갑니다.
->
이부분은 해당 해설강의내에서 설명되고 있는데 혹시 강의보시고도 이해가 안되실까요?
감사합니다.
안녕하세요 유태님 ㅎㅎ
역으로 도착점이 시작점 역할을 하게 된 것인가요?
-> 네 맞습니다.
일단 a -> c로 가는 건 이해하실 것 같습니다. 자 여기서 c -> a를 구해야 하는데요.
c -> b -> a라는 간선을
a -> b -> c로 바꿔버리는 것입니다.
adj2[v].push_back(make_pair(w, u)); 그 다음에 a -> c 를 구하면 사실 c -> a를 구하게 되는 것과 같게 되는 것입니다.
dijkstra(dist2, adj2);
for(int i = 1; i <= N; i++){
if(i == X) continue;
ret = max(ret, dist[i] + dist2[i]);
}
감사합니다.
0
안녕하세요, 인프런 AI 인턴입니다. 한유태님.
다익스트라 알고리즘을 활용한 최단 거리 문제에 대해 질문 주셨군요. 선생님의 강의에서 사용된 방법과의 차이점에 대해 설명 드리겠습니다.
일반적으로 다익스트라 알고리즘은 하나의 시작점에서 다른 모든 노드로의 최단 거리를 구하는 데 사용됩니다. 하지만 두 번의 다익스트라 알고리즘을 활용하면 문제를 더 효율적으로 풀 수 있습니다. X번 마을을 기준으로 다익스트라를 또 한 번 수행하여 반대 방향의 최단 거리를 구할 수도 있습니다. 이를 통해 학생들이 X번 마을로 오고 각자의 마을로 돌아가는데 걸리는 총 최단 시간을 계산할 수 있습니다.
따라서, 다음과 같은 방법으로 접근할 수 있습니다.
1. 다익스트라 알고리즘을 이용해 X번 마을로 가는 경로의 최단 거리를 구합니다.
2. 반대 방향(다시 각자의 마을로 돌아가는 경로)으로의 다익스트라 알고리즘을 수행합니다. 이 경우에는 거리 그래프의 방향을 뒤집어서 계산합니다.
이 과정을 통해 모든 학생의 왕복 거리 합이 계산되며, 그 중 최댓값을 구하여 문제를 해결할 수 있습니다. 한 번의 다익스트라로 시작하는 위치에서 나머지 모든 위치로의 최단 거리를 구하고, 반대 방향에서도 동일한 과정을 반복한다는 점이 핵심입니다.
아래 링크를 통해 더 많은 정보와 출발점에 대한 이해를 도와드릴 수 있습니다:
- 8-R 다익스트라 2번 사용 풀이 질문입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
네.. 제가 느끼기엔 설명이 부족한 것 같습니다.
다익스트라 함수 안에서 dist배열 초기화는 공통으로 dist[X] = 0;으로 되어있습니다. 이 부분은 시작점이 X일 때 사용하는 것으로 알고 있는데요, 1번 로직은 1~N까지의 시작점들이 있고, X라는 도착점이 있습니다.
이해가 되지 않아 좀더 코드를 분석해봤는데요, 차이점은 adj[도착점].push_back(make_pair(가중치, 시작점));을 넣어주신 부분 하나였습니다. 이 코드로 인해서 역으로 도착점이 시작점 역할을 하게 된 것인가요?