백준

1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 문제 N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오. 풀이 다솜이가 기부할 수 있는 랜선의 길이는 자신의 N개의 컴퓨터를 랜선으로 연결하고 남는 랜선을 기부할 수 있다. 이때, 최대로 기부할 수 있는 랜선의 길이는 자신의 N개의 컴퓨터를 최단 거리의 랜선으로 연결하고 연결하지 않는 남은 랜선을 기부할 수 있다. 따라서 랜선들로 스패닝 트리를 구성하고 스패닝 트리를..

1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 풀이 📌 유니온 파인드 static void union(int a, int b){ int x = find(a); int y = find(b); A[y] = x; } static int find(int a){ if(A[a] == a) return a; else{ A[a] = find(A[a]); return A[a]; } } f..

1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제 BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오. 풀이 이 문제는 친구 관계의 케빈 베이컨의 법칙을 적용하여 거리를 구했을 때 다른 모든 친구로의 거리가 가장 짧은 사람 번호를 구하는 문제이다. 모든 정점들에 대해서 다른 모든 정점으로의 케빈 베이컨 수(거리)를 구해야 하는 문제였기 때문에 플로이드-워셜 알고리즘을 사용하여 문제를 풀었습..

11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 풀이 주어진 정점들에 대해서 다른 모든 정점으로 가는 경로가 있는지 여부에 대한 출력을 하는 문제입니다. 저는 모든 정점들에 대해서 다른 모든 정점으로의 경로 였기 때문에 플로이드-워셜 알고리즘을 사용하여 문제를 해결하였습니다. 📌 입력 int[][] A = new int[N][N]; StringTokenizer st; for..

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 모든 도시에 대해서 다른 모든 도시로의 최단 거리를 구하는 문제입니다. 플로이드-워셜 알고리즘을 통해 문제를 해결하였습니다. 풀이 플로이드-워셜 플로이드-워셜 알고리즘은 모든 도시에 대해서 다른 모든 도시로의 최단 거리를 구하는 문제입니다. 이 거리는 음수 가중치가 있더라도 동작하며 시간 복잡도는 $O(N^3)$으로 매우 큰 편입니다. 따라서 입력 정점이 작다는 특징도 있습니다. 플로이드 워셜은 다음과 같은 단계를 통해 값을 구해냅니다. 모든 도시에 대해서 ..

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 문제 도시들과 도시들 사이에 지나는 버스 그리고 버스가 목적지 도시로 이동하는데 걸리는 시간이 주어졌을 때 최단 거리를 구하여라 단, 버스들은 음의 시간을 지나는 시간이 있을 수 있다. 즉, 시간을 거슬러올라가는 타임머신 버스가 있다. 풀이 해당 문제는 음의 가중치가 존재하기 때문에 다익스트라로는 해결할 수 없고 벨만-포드 알고리즘을 통해 풀어야 합니다. 벨만-포드 알고리즘 벨만-포드 알고리즘은 전체 노..

1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 도시들이 주어지고 도시들을 연결해주는 버스가 주어졌을 때 출발지 도시에서 목적지 도시까지의 최단 거리를 구하여라. 풀이 최적화된 다익스트라 알고리즘 설명 [JAVA] 백준 1753 다익스트라 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 g-..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 방향그래프가 주어졌을 때 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 풀이 하나의 출발점에서 다른 모든 노드로 향하는 최단 거리를 구하라는 문제이기 때문에 다익스트라 알고리즘을 사용하여 풀었습니다. 📌 입력 boolean[] V = new boolean[N]; ArrayList[]A = new ArrayList[N]; int[] distance = new int[N]; for(int i=1..