백준 그래프 이론

    [백준, 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 14676] 영우는 사기꾼? (java)
    Problem Solving/BOJ

    [백준, BOJ 14676] 영우는 사기꾼? (java)

    https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 메모리: 73,964 KB , 시간: 568 ms 사용 알고리즘: 방향 비순환 그래프, 그래프 이론, 구현 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main ..

    [백준, 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[] ..

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

    [백준, BOJ 17396] 백도 (java)

    https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 메모리: 134,104 KB , 시간: 992 ms 사용 알고리즘: 데이크스트라, 그래프 이론, 최단 경로 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue..

    [백준, BOJ 4386] 별자리 만들기 (java)
    Problem Solving/BOJ

    [백준, BOJ 4386] 별자리 만들기 (java)

    https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 메모리: 14,540 KB , 시간: 140 ms 사용 알고리즘: 그래프 이론, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; public class..

    [백준, BOJ 1916] 최소비용 구하기 (java)
    Problem Solving/BOJ

    [백준, BOJ 1916] 최소비용 구하기 (java)

    https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 메모리: 51,460 KB , 시간: 460 ms 사용 알고리즘: 데이크스트라, 그래프 이론, 최단 경로 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQu..

    [백준, BOJ 1368] 물대기 (java)
    Problem Solving/BOJ

    [백준, BOJ 1368] 물대기 (java)

    https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 메모리: 25,316 KB , 시간: 356 ms 사용 알고리즘: 그래프 이론, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { ..

    [백준, BOJ 14267] 회사 문화 1 (java)
    Problem Solving/BOJ

    [백준, BOJ 14267] 회사 문화 1 (java)

    https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 메모리: 53,272 KB , 시간: 580 ms 사용 알고리즘: 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) ..

    [백준, BOJ 14567] 선수과목 (Prerequisite) (java)
    Problem Solving/BOJ

    [백준, BOJ 14567] 선수과목 (Prerequisite) (java)

    https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 메모리: 126,016 KB , 시간: 580 ms 사용 알고리즘: 방향 비순환 그래프, 다이나믹 프로그래밍, 그래프 이론, 위상 정렬 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static int N; static ArrayList preSubject; static int[] p..

티스토리툴바