최소 스패닝 트리2 [자바] 백준 1647 - 도시 분할 계획 (java) 문제 : boj1000 필요 알고리즘 개념 최소 스패닝 트리 (MST; minimum spanning tree) 너무 대놓고 최소 스패닝 트리 문제이다. MST에 대한 개념이 문제를 푸는데 필요하다. 크루스칼, 프림 MST를 구하기 위한 알고리즘이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 너무 대놓고 MST 구하고, 그 중 가장 큰 간선 하나 제거하라는게 느껴지는 문제라 좀 아쉬웠다. 우선 스패닝 트리란, 모든 정점.. 2022. 9. 2. 백준 4386 자바 - 별자리 만들기 (BOJ 4386 JAVA) 문제 : boj4386 1. 모든 별을 이어야하고, 최소 비용을 구해야 한다. 따라서 N개의 정점(별)에 대해 이은 간선이 N-1개(모든 정점을 포함하려면 최소 N-1개의 간선이 필요하고, 최소비용을 위해서는 거기서 하나라도 간선이 추가되선 안되므로) 이어야만 모든 별을 이으면서 최소 비용이 가능하다. 따라서 Spanning Tree를 구성해야 하고, 최소 비용이어야 하므로 MST (Minimum Spanning Tree)를 구하는 문제임을 알 수 있다. 후보군이 될 간선은 N개에 대해 다른 N-1개 모두로의 간선이므로 간선은 총 N*(N-1)개 존재할 수 있다. 이 중 N-1개를 골라 MST를 만들었을 때의 최소 비용이 답이다. 2. 대표적인 MST 알고리즘에는 Prim과 Kruscal이 있다. 이 문.. 2022. 1. 12. 이전 1 다음
