새벽 기상을 꿈꾸는 루민

이번 포스팅에서 풀어본 문제는 "전기가 부족해"라는 문제입니다. 1. 문제 2. 입출력 및 예제 3. 문제 풀이 이번 문제는 가장 중요한 것이 3개의 발전소로 나눈다는 것이다. 따라서 이번 문제에서는 find를 이용하여 정점들을 탐색할 때 탐색한 경우 체크하는 것이 중요하다 . 아래의 그림을 통해서 이해해보자 위의 그림처럼 가정하여 풀어보도록 하자. 처음에는 발전소를 선택하지 않았기 때문에 모두 0의 값을 가진다. 발전소를 1,2,9번으로 선택하고 진행할 예정이다. 발전소를 선택했을 때 해당 발전소의 값(index)에는 체크를 해두면 된다. 양수의 값의 경우 겹칠 수 있기 때문에 음수의 값으로 체크하는 것이 중요하다.(boolean으로도 가능) 가장 짧은 간선인 2를 이어주고 7에 체크를 해준다. 다음으..

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

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

이번 포스팅에서는 최소 스패닝 트리 문제를 풀어보겠습니다. 1. 문제 2. 예제 3. 문제 풀이 이번 문제는 최소 스패닝 트리를 구하면 되는 문제이다. 위의 그림처럼 가중치 C가 최소인 값으로 구성된 트리를 구하면 되는데 이 또한 기존에 풀었던 union-find 알고리즘을 그대로 사용하면 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.StringTokenizer; import jav..

이번 포스팅에서는 도시 분할 계획 문제를 풀어보겠습니다. 1. 문제 2. 입출력 및 예제 3. 문제 풀이 이번 문제는 네트워크 연결(1922번)문제와 유사하게 접근하면 쉽게 풀 수 있습니다. 자세한 1922번 문제 풀이는 아래 링크로 남겨보겠습니다. [백준] 1922번 네트워크 연결 문제 풀기(Java) - 세무민의 코딩일기 이번 포스팅은 알고리즘 문제 풀이 포스팅입니다. 이번 문제는 네트워크 연결이라는 문제입니다. 1. 문제 설명 2. 입출력 예제 3. 문제 풀이 위의 그림을 보면 모든 컴퓨터가 최소 비용으로 연결 sg-moomin.tistory.com 문제 풀이의 결론을 말하자면 도시를 2개로 분할시키면 됩니다. 유지비의 합을 최소로 할 수 있도록 하되 도시를 2개로 분할하려면 방법은 한개의 도시로 ..

이번 포스팅은 알고리즘 문제 풀이 포스팅입니다. 이번 문제는 네트워크 연결이라는 문제입니다. 1. 문제 설명 2. 입출력 예제 3. 문제 풀이 위의 그림을 보면 모든 컴퓨터가 최소 비용으로 연결되기 위한 방법은 위와 같을 것이다. 이번 문제에서 가장 중요한 포인트는 모든 컴퓨터를 연결하는데 필요하는 최소비용입니다. 여기서 알 수 있는 건 Kruskal-MST를 이용하여 문제를 풀 수 있다는 것입니다. Kruskal-MST는 최소 비용 신장 트리를 만든되 사이클이 생성되면 안되며 최소 비용이여 하는 것입니다. 따라서 Kruskal-Mst를 이용하면 문제를 풀 수 있습니다. package backjoon_20210920; import java.io.BufferedReader; import java.io.Bu..