반응형 그래프 탐색1 [C/C++] 백준 #1939 중량제한(그래프) 이번 문제는 프림이나 다익스트라와 비슷하게 동작하지만, 경로에 걸쳐있는 간선중, 최소값의 간선값이 해당 경로값이 됩니다. 이 경로값이 가장 큰 것을 찾는 문제입니다. 그래서 프림 알고리즘이나 다익스트라 알고리즘을 곧이 곧대로 사용할 수가 없습니다. 제가 사용한 탐욕 방법은 이것입니다. 0) 모든 노드의 값을 0으로 초기화합니다. 1) 출발지점에서 가장 큰 노드값을 가지고 있는 노드를 선택합니다. 2) 이동할 수 있는 모든 간선들을 적용하여 도착할 곳의 노드값을 결정합니다. 도착할 노드값은 현재보다 큰 경우 노드값을 저장하고, 우선순위큐에 해당 값을 넣습니다. 3) 도착지점이 가장 큰 노드값인 경우 종료합니다. 이 상태에서 선택할 수 있는 다른 노드값은 도착지점보다 적은 값이므로 의미가 없습니다. 제가 작.. 2022. 11. 19. 이전 1 다음 728x90
