새벽 기상을 꿈꾸는 루민

이번 포스팅에서 다룰 문제는 나만 안되는 연애 문제 입니다. 1. 문제 2. 입출력 및 예시 3. 문제 풀이 이번 문제에서 3가지의 특징을 잘 분석하면 된다. 1. 남초 대학교와 여초 대학들을 연결하는 도로만 이루어져 있다. -> 이말은 즉 2가지의 정점으로 구분된다는 의미 2. 사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서 모든 대학교로 이동 가능하다. -> 모든 정점들이 모두 이어져서 있어야 한다는 것, 즉 트리형태 3. 시간낭비하지 않고 경로의 최단거리를 구해야 한다. -> 최소 스패닝 트리 4. 모든 학교를 연결하는 경로가 없을 경우 -1을 출력한다. -> 학교 정점 == 입력받은 학교의 수 - 1 우선 위의 포인트를 잘 이해하면 문제를 쉽게 접근할 수 있다. 그래도 이번 문제를 풀기..

이번 포스팅에서 다룰 문제는 별자리 만들기 입니다. 1. 문제 2. 입출력 및 예시 3. 문제 풀이 이번 문제에서 포인트는 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있다는 말이다. 이 말은 즉 그래프 형태이면서 간접적으로 연결되어 있다는 것은 부모가 연결되어 있으면 연결되어 있는 구조이다. 이 문제는 최소 스패닝 트리 문제와 동일하다. 따라서 Kruskal-Mst 알고리즘을 이용해서 문제를 풀면 된다. 그렇지만 문제를 풀다보면 기존에는 결과값을 주었지만 이 문제는 주지 않았다. 그 말은 해당 정점들의 간선 길이를 내가 직접 구해야 한다는 말이다. 아래의 그림을 보면서 한번 이해해보자. 위의 예시대로 그림을 그려봤다. 정점들을 그린 뒤 간선을 하나씩 이어봤다. 간선을 이어봤다면 이제 ..