인프런 커뮤니티 질문&답변
작성한 질문수
7-A 질문이 있습니다 !
작성
·
445
0
선생님 7-A에서 경로를 계산할 때 순서는 상관이 없다고 하셨는데..
각 경로 방향마다 가중치값이 다른데 어떻게 순서가 상관이 없나요??
각 경로마다 모든 경우의 수를 계산해서 최솟값을 계산해야하는거아닌가요? ㅠㅠ
예를 들면 도시 A,B,C가 있다고 가정할 때
A B C
A C B
B A C
B C A
C A B
C B A
각 경로 가중치 합이 다르지 않나요 ?
그래서 저는 왜 시작 정점을 하나로만 계산하는지도 잘 이해가 안갑니다 ㅠㅠ
답변 1
0
큰돌
지식공유자
안녕하세요 유하님 ㅎㅎ
이렇게 생각하면 쉬워요.
B - A - C 로 연결이 되어있어요.
저의 화가수준의 그림을 준비했어요.
자 이렇게 연결이 되어있겠죠?
어차피 이 문제의 경우 하나의 최적해만 찾으면 되기 때문에 이 경로가 최적해라고 해볼게요.
이 때 B - A - C든, A - C - B든 구하는 순서는 달라도 되겠죠?
그래서 그냥 A부터 시작해도 되는 것입니다. 어차피 A를 무조건 포함해야 하기 때문이죠.(문제에서는 1번노드)
또 질문 있으시면 언제든지 질문 부탁드립니다.
감사합니다.
강사 큰돌 올림.
우와~ㅎㅎ 제 이름 어떻게 아셨어요~?! ㅎㅋㅋㅎ
감사합니다 ㅎㅎ 쌤의 화가 뺨치는 그림 실력 덕에
이해가 쏙쏙 갔습니당ㅎㅎ
하다가 모르는 게 생기면 또 여쭤볼게요 !
새해 복 많이 받으세요 ~~!!