dfs2 [백준] 28146 - Broken Minimum Spanning Tree (c++) https://www.acmicpc.net/problem/28146 문제 요약N개의 정점과 M개의 간선으로 구성된 무향 가중치 그래프와 스패닝 트리 S가 주어진다. S를 MST로 만들기 위해 최소한의 간선 스왑을 수행하는 과정을 출력하라.간선 스왑이란, 스패닝 트리에서 간선 하나를 제거하고 스패닝 트리 상태를 유지하면서 그래프의 다른 간선을 추가하는 동작이다. 풀이 (M^2)MST트리 셋DFS크루스칼을 한 번 돌리는데 정렬에서 가중치가 같을 때 S의 간선이 우선이 되게 한다. 이렇게 얻은 MST에서 S에 포함되지 않는 간선을 하나씩 추가한다. 간선을 추가하면 사이클이 하나 생기는데 DFS로 가중치가 최대인 간선을 찾아 삭제하면 된다. 간선을 추가하고 삭제하는 것은 트리 셋으로 할 수 있다.#includ.. 2025. 1. 23. [백준] 3267 - TWO (c++) https://www.acmicpc.net/problem/3267 Croatian Highschool Competitions in Informatics > 2002 > National Competition #2 - Seniors 3번 문제 요약청소부 두명이 트리를 청소하려고 한다. 주어진 트리에서 모든 간선을 한 번 이상 거치면 청소를 마쳤다고 한다. 트리와 청소부의 시작 위치가 주어질 때 청소부가 청소를 마치는데 걸리는 최소 시간을 구해라. 풀이 (M+N)DFS한 번만 거치는 간선이 있고 왕복을 해야 하는 간선이 있을 것이다. 한 번만 거치는 길이가 클 수록 좋기 때문에 트리의 지름을 구해준다. 지름에 포함되지 않는 간선은 모두 왕복해야 하기 때문에 답은 ((가중치 총합-지름)*2+지름)이 된다. 시작.. 2024. 11. 20. 이전 1 다음