백준 최소 스패닝 트리

    [백준, BOJ 14950] 정복자 (java)
    Problem Solving/BOJ

    [백준, BOJ 14950] 정복자 (java)

    https://www.acmicpc.net/problem/14950메모리: 26,704 KB , 시간: 376 ms사용 알고리즘: 그래프 이론, 최소 스패닝 트리처음에 다익스트라로 풀었다가, 알고리즘 분류를 보고 크루스칼 알고리즘으로도 풀 수 있겠다고 알게 돼서 다시 크루스칼로 풀었다...알고리즘 며칠 안 했다고 이전에는 당연히 크루스칼로 풀었을 문제를 다익스트라로 풀었네,,import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { static int[] parent; public static..

    [백준, BOJ 1045] 도로 (java)
    Problem Solving/BOJ

    [백준, BOJ 1045] 도로 (java)

    https://www.acmicpc.net/problem/1045메모리: 16,000 KB , 시간: 152 ms사용 알고리즘: 그래프 이론, 그리디 알고리즘, 최소 스패닝 트리import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main { static int[] parent; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(ne..

    [백준, BOJ 1414] 불우이웃돕기 (java)
    Problem Solving/BOJ

    [백준, BOJ 1414] 불우이웃돕기 (java)

    https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 메모리: 14,388 KB , 시간: 136 ms 사용 알고리즘: 그래프 이론, 최소 스패닝 트리, 문자열 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; public class Main { static int[] parent; public static void mai..

    [백준, BOJ 10423] 전기가 부족해 (java)
    Problem Solving/BOJ

    [백준, BOJ 10423] 전기가 부족해 (java)

    https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 메모리: 47,436 KB , 시간: 560 ms 사용 알고리즘: 그래프 이론, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class ..

    [백준, BOJ 1944] 복제 로봇 (java)
    Problem Solving/BOJ

    [백준, BOJ 1944] 복제 로봇 (java)

    https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 메모리: 54,700 KB , 시간: 376 ms 사용 알고리즘: 너비 우선 탐색, 그래프 이론, 그래프 탐색, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static int N, M; static char..

    [백준, BOJ 17490] 일감호에 다리 놓기 (java)
    Problem Solving/BOJ

    [백준, BOJ 17490] 일감호에 다리 놓기 (java)

    https://www.acmicpc.net/problem/17490 17490번: 일감호에 다리 놓기 2번, 4번, 5번 강의동과 와우도를 연결하면 가지고 있는 돌 내에서 징검다리를 완성할 수 있다. 이 때, 어떤 한 강의동에서 다른 모든 강의동으로 가는 길이 존재한다. www.acmicpc.net 메모리: 373,380 KB , 시간: 1,816 ms 사용 알고리즘: 자료 구조, 그래프 이론, 그리디 알고리즘, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer;..

    [백준, BOJ 2406] 안정적인 네트워크 (java)
    Problem Solving/BOJ

    [백준, BOJ 2406] 안정적인 네트워크 (java)

    https://www.acmicpc.net/problem/2406 2406번: 안정적인 네트워크 첫째 줄에 두 정수 n(1 ≤ n ≤ 1,000), m(0 ≤ m ≤ 10,000)이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서 www.acmicpc.net 메모리: 104,684 KB , 시간: 1,136 ms 사용 알고리즘: 그래프 이론, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.uti..

    [백준, BOJ 13418] 학교 탐방하기 (java)
    Problem Solving/BOJ

    [백준, BOJ 13418] 학교 탐방하기 (java)

    https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 메모리: 171,416 KB , 시간: 1,084 ms 사용 알고리즘: 그래프 이론, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class M..

    [백준, BOJ 18769] 그리드 네트워크 (java)
    Problem Solving/BOJ

    [백준, BOJ 18769] 그리드 네트워크 (java)

    https://www.acmicpc.net/problem/18769 18769번: 그리드 네트워크 재현이는 그리드 네트워크 컨설팅 회사를 운영하고 있다. 어떤 회사의 데이터 서버가 격자 형태의 그래프로 주어졌을 때, 최소의 비용을 들여서 전용 통신망을 설치하려고 한다. 이때, 전용 통 www.acmicpc.net 메모리: 312,128 KB , 시간: 2,128 ms 사용 알고리즘: 그래프 이론, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { static int[] ..

    [백준, BOJ 16202] MST 게임 (java)
    Problem Solving/BOJ

    [백준, BOJ 16202] MST 게임 (java)

    https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 메모리: 21,028 KB , 시간: 288 ms 사용 알고리즘: 그래프 이론, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[] ..

티스토리툴바