백준 그래프 이론

    [백준, BOJ 14621] 나만 안되는 연애 (java)
    Problem Solving/BOJ

    [백준, BOJ 14621] 나만 안되는 연애 (java)

    https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 메모리: 20,416 KB , 시간: 232 ms 사용 알고리즘: 그래프 이론, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class M..

    [백준, BOJ 16398] 행성 연결 (java)
    Problem Solving/BOJ

    [백준, BOJ 16398] 행성 연결 (java)

    https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 메모리: 123,600 KB , 시간: 1,080 ms 사용 알고리즘: 그래프 이론, 최소 스패닝 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { static int[] p..

    [백준, BOJ 1240] 노드사이의 거리 (java)
    Problem Solving/BOJ

    [백준, BOJ 1240] 노드사이의 거리 (java)

    https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 메모리: 51,152 KB , 시간: 388 ms 사용 알고리즘: 너비 우선 탐색, 그래프 이론, 그래프 탐색, 트리 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; ..

    [백준, BOJ 11657] 타임머신 (java)
    Problem Solving/BOJ

    [백준, BOJ 11657] 타임머신 (java)

    https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 메모리: 239,476 KB , 시간: 896 ms 사용 알고리즘: 벨만-포드, 그래프 이론, 최단 경로 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java...

    [백준, BOJ 1956] 운동 (java)
    Problem Solving/BOJ

    [백준, BOJ 1956] 운동 (java)

    https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 메모리: 58,544 KB , 시간: 612 ms 사용 알고리즘: 플로이드-워셜, 그래프 이론, 최단 경로 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { ..

    [백준, BOJ 1774] 우주신과의 교감 (java)
    Problem Solving/BOJ

    [백준, BOJ 1774] 우주신과의 교감 (java)

    https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 메모리: 49,552 KB , 시간: 732 ms 사용 알고리즘: 그래프 이론, 스패닝 트리, 크루스칼 알고리즘 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static int[] parent; public static void ..

    [백준, BOJ 27653] 최소 트리 분할 (java)
    Problem Solving/BOJ

    [백준, BOJ 27653] 최소 트리 분할 (java)

    https://www.acmicpc.net/problem/27653 27653번: 최소 트리 분할 정점이 $N$개인 트리가 주어진다. 정점에는 $1$부터 $N$까지 번호가 붙어있다. 각 정점에는 가중치가 존재하는데, 초기에 모든 가중치는 $0$이다. 당신은 다음 연산을 트리에 반복하여 $1$ 이상 $N$ www.acmicpc.net 메모리: 69,668 KB , 시간: 732 ms 사용 알고리즘: 넓이 우선 탐색, 그래프 이론, 그래프 탐색 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; imp..

    [백준, BOJ 1937] 욕심쟁이 판다 (java)
    Problem Solving/BOJ

    [백준, BOJ 1937] 욕심쟁이 판다 (java)

    https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 메모리: 50,636 KB , 시간: 812 ms 사용 알고리즘: 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { st..

    [백준, BOJ 20924] 트리의 기둥과 가지 (java)
    Problem Solving/BOJ

    [백준, BOJ 20924] 트리의 기둥과 가지 (java)

    https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.u..

    [백준, BOJ 2224] 명제 증명 (java)
    Problem Solving/BOJ

    [백준, BOJ 2224] 명제 증명 (java)

    https://www.acmicpc.net/problem/2224 2224번: 명제 증명 첫째 줄에 출력할 명제의 개수 X개를 출력한다. 다음 X개의 줄에 증명될 수 있는 명제를 한 줄에 하나씩 출력한다. 명제를 출력할 때에는 전건 순으로 정렬하고, 전건이 같은 경우에는 후건 순으 www.acmicpc.net import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBu..

티스토리툴바