배울점
- 1) 중복되는 2개의 정점의 cost 를 어떻게 넣을 것인가?
- 2) 문제 이해를 못했는데, 멘탈 잡고 어떻게 할 것인가?
- 문제의 입력 예제만 보는 것이 아니라 상상을 해보자.
문제에서 말하는 바는
-
왜 최적화 결정문제냐면?
: 다리의 길이는 주어졌지만, 물품 중량의 최대값은 알 수 없기 때문이다. -
그리고 startV 와 endV를 직접적으로 연결하는 것만 확인하는 것이 아닌 돌고 돌아오는 것들도 염두해야 한다.
문제 이해를 못함.
- 맨 처음에 왜 그런지는 모르겠지만,
1 번 3번 공장을 무시하고...
2 3 2 번이 마지막이니까. 2번과 3번 공장간에 경로를 생각했다.. ㅡㅡ;;;
-
문제에서 구하고자 하는 바는 2개의 공장을 가로지를 수 있는 물품의 최대값이다.
-
주어진 입력예제를 통해서 그럼 그냥 3 아니야?
-
단순하게 이렇게 생각을 했는데, 굳이 아래의 1 - 3 양방향 만의 다리만 존재하는 것이
아닌 공장이 아닌 다른 섬들과의 다리를 이용해서 1번에 있는 공장에서부터 시작해 3번공장
까지 갈 수 있는 모든 경우의 수중에서의 -
최대 물품이라는 것이다.
- 일단은 양방향이라는 것을 염두하자.
- 예를 들면 1번에서 3번이라고 치고,
1 - 2 : 50
1 - 3 : 4
2 - 3 : 70 이라고 한다면 어떻게 할 것인가?
1 - 2 - 3 번 도로를 이용해서 1번에서 3번까지 공장으로 가는 순간이 최고의 경로가 될것이고, 이때 의 물품의 최대 용량은 50이다.
레벨업하기
-
문제에서 주어진 입력예제가 아닌 다른 예시를 생각해보자.
-
-> 어렵게 생각하는 것이 아니라, 이러면 어떻게 될까? 저러면 어떻게 될까?
를 생각하는 자세를 가지자.
중복되는 2개의 정점 어떻게 처리.
- startV에서 endV 까지의 dist가 여러개 일수 있따고 해서 이렇게 작성함.
- 특정 물품의 target이 정해졌을 때 , 연결된 다리의 weight이 target보다 커야만
해당 물품은 다리를 건널 수 있다.
🔥🔥🔥