플로이드–워셜4 [백준] 2458: 키 순서 - JAVA https://www.acmicpc.net/problem/2458 풀이1 ~ n번 학생들에 대해 m개의 관계가 주어지는데, 각각의 관계에는 a번 학생이 b번 학생보다 작다는 것을 알려준다. 이 관계들을 이용해 자신이 몇 번째 등수인지 정확히 알 수 있는 사람의 수를 세는 문제이다. 모든 정점끼리 탐색을 해야하기 때문에 플로이드-워셜 알고리즘을 사용했다. 플로이드-워셜은 O(n^3)의 시간복잡도를 갖는다. 핵심 로직은 다음과 같다.for (int k = 0; k i와 k가 연결되어있고, k와 j가 연결되어 있다면, i와 j는 연결되었다고 보는 것이다. 모든 정점끼리 연결 여부를 체크했다면 각 학생별로 연결된 학생의 수가 n-1인지 확인하면 된다. 메모리: 36932KB시간: 604ms언어: Java 11.. 2024. 5. 19. [백준] 1956: 운동 - JAVA https://www.acmicpc.net/problem/1956 풀이v개의 정점과 e개의 간선이 주어진다. 출발점에서 다시 출발점으로 돌아오는 사이클이 있는지, 있다면 최솟값을 구하는 문제이다. 모든 정점에서 다른 모든 정점까지의 최단경로가 필요하다. -> 플로이드 워셜 알고리즘을 사용한다. 원래 알고있던 플로이드 워셜에서는 거리를 저장할 이차원배열을 만들고, 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화를 했었다. 하지만 이 문제에서는 자기 자신에서 자기 자신으로 돌아와야하므로 다른 값들과 마찬가지로 INF로 초기화하였다. 그리고나서 플로이드 워셜 알고리즘을 통해 i정점에서 k를 거쳐 j로 이동하는 최솟값을 갱신해주면 자기 자신으로 다시 돌아오는 거리도 갱신된다. `dist[i][i]` 중 .. 2024. 5. 17. [백준] 11562: 백양로 브레이크 - JAVA https://www.acmicpc.net/problem/11562 풀이일방통행인 길을 양방향으로 바꿔 목적지로 갈 수 있도록 해야한다. 플로이드-워셜 알고리즘을 사용하는데 일방통행인 길은 양방향으로 바꿔줘야하므로 1이라는 가중치를 두고, 양방향길은 0으로 저장한다. 플로이드-워셜 알고리즘으로 u에서 v로 가는데 바꿔야 할 길의 수를 구해놓고 질문이 올 때마다 저장된 배열에서 값을 출력한다. 메모리: 31772KB시간: 440ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br .. 2024. 5. 14. [백준] 1613: 역사 - JAVA https://www.acmicpc.net/problem/1613 풀이사건들의 전후관계를 확인하는 문제이다. 이차원배열을 만들어 a사건 이후에 b사건이 이루어진다면 arr[a][b]를 true로 저장했다. 이때 플로이드-워셜 알고리즘을 사용했다.for (int k = 1; k 배열을 다 채운 후 입력을 받으면서 table[a][b]가 true이면 -1, table[b][a]가 true이면 1, 둘 다 false이면 0을 출력했다. 메모리: 38252KB시간: 472ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 5. 14. 이전 1 다음