반응형 차량 모듈 제작1 백준 28297번 : 차량 모듈 제작(C/C++) 백준 28297번 : 차량 모듈 제작(C/C++) 기하와 최소신장트리 문제이다. 원을 그래프의 노드로 보고, 컨베어 벨트의 길이를 간선의 길이로 보면 최소 길이의 컨베어 벨트로 모든 원을 연결 하는 문제로 볼 수 있다. (최소 신장 트리) 임이의 두 원이 겹친다면 바로 union해주고 간선의 길이는 0으로 셋팅한다. 임이의 두 원이 겹치지 않는다면 아래 식을 통해 간선의 길이를 계산해주면 된다. 이후 크루스칼 알고리즘을 이용하여 최소신장트리의 길이를 출력하면된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 4.. 2023. 7. 2. 이전 1 다음 반응형
