알고리즘148 [JAVA]백준_11403_경로찾기 문제링크 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main_11403 { //가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j.. 2021. 4. 21. [JAVA]백준_11562_백양로 브레이크 문제링크 https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 양방향의 경우 u->v로 가는 길은 무조건 존재한다. -->비용이 없다고 생각하고 0으로 표시 단방향의 경우 v->u로 연결된 길이 없다 -> 가는데 1의 비용이 발생한다고 생각 (가는데 연결해야 되는 단방향의 경우의 수를 구하면 됨으로) floyd 알고리즘 적용 package BOJ; import java.io.*; import java.util.Arrays; import java.u.. 2021. 4. 21. [JAVA] KRUSKAL && PRIM 최소 신장 트리 (MST) 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 KRUSKAL 알고리즘 간선을 하나씩 선택해서 MST를 찾는 알고리즘이다. 모든 간선을 가중치에 따라 오름차순으로 정렬한다. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다. 단 사이클이 존재할 시 다음으로 가중치가 낮은 간선을 선택한다. n-1개의 간선이 선택될 때까지 위의 과정을 반복한다. PRIM 알고리즘 KRUSKAL과 달리 임의의 정점을 하나 선택해서 시작한다. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택한다. 모든 정점이 선택될 때 까지 위의 과정을 반복한다. PRIM 에서는 서로소인 2개의 집합 정보를 유지한다. 1.트리 정점(MST)를 만들.. 2021. 4. 20. [JAVA]백준_2646_치즈 문제링크 https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 풀면서 고민을 했던 부분 -> 밀폐된 공간을 어떻게 표현할 것인가,,? 이 부분은 0인 부분을 BFS로 처리하였다. 보통 알고리즘 문제는 1인부분?으로 주로 BFS를 타고 들어가기 때문에 생각하는데 조금 시간이 걸렸던거같다. 0부터 BFS로 타고들어가면서 만약 1(치즈)를 만나면 큐에 넣어주지않는 방식으로 진행하면 밀폐된 공간을 찾을 수 있다. package BOJ; import java.io.B.. 2021. 4. 19. [JAVA]백준_11724_연결요소의 개수 문제링크 http://acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; impo.. 2021. 4. 19. [JAVA]백준_1012_유기농배추 문제링크 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net package BOJ; import java.io.*; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main_1012 { static int N,M,K; static int map[][]; static boolean isVi.. 2021. 4. 19. [JAVA]백준_2606_바이러스 문제링크 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; pub.. 2021. 4. 18. [JAVA]백준_2458_키순서 문제링크 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer.. 2021. 4. 18. [JAVA]백준_7662_이중 우선순위 큐 문제링크 https://www.acmicpc.net/problem/7662 package BOJ; import java.io.*; import java.util.*; //7662 이중 우선순위 큐 public class Main_7662 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); for(int t=0;t 2021. 4. 18. 이전 1 2 3 4 5 6 7 8 ··· 17 다음
