플로이드 워셜 알고리즘5 [백준] 21940번 - 가운데에서 만나기 [Java] https://www.acmicpc.net/problem/21940 1. 아이디어 1번 도시와 준형이와 친구들이 사는 K개의 도시들과 왕복 시간의 최댓값, 2번 도시와 준형이와 친구들이 사는 K개의 도시들과 왕복 시간의 최댓값, 이렇게 최댓값 중 최솟값을 구해야하는 문제로 N이 최대 200여서 플로이드 워셜 알고리즘으로 도시 간 최단거리를 미리 구한 후 이를 반복적으로 사용하면 간단하게 해결할 수 있다.2. 문제풀이 플로이드 워셜 알고리즘으로 각 도시 간 최단 시간을 저장한 dp 테이블을 생성했다. 이후 행은 1번부터 N번 도시, 열은 준형이와 친구들이 사는 도시로 하는 거리 배열 dist를 만들어서 이 dist에 dp배열을 통해 왕복 시간을 저장했다. 이후 이를 정렬해서 최댓값들 중 최솟값을 찾고 이.. 2025. 2. 10. [백준] 11780번 - 플로이드 2 [Java] https://www.acmicpc.net/problem/11780 1. 아이디어 이전 플로이드 문제에서 경로 출력까지 추가된 문제로 최단 거리를 갱신할 때 방문한 경유지 정보를 기록하는 before 배열을 활용하면 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 11404번 - 플로이드 [Java])2. 문제풀이 경로 입력 단계에서 before 배열을 초기화한 후 3중 반복문에서 경유지를 방문한 경로가 더 짧을 경우 dp 테이블 갱신 후 before 배열에서 before[i][j] = before[k][j]로 i에서 j로 가기 위한 경로에 k에서 j로 가는 경로를 저장해줬다. 이후 이를 역순으로 조회하면 경로를 얻을 수 있고 출력을 위해 Stack 자료구조와 StringBuilder를 활용했다.. 2025. 2. 2. [백준] 14938번 - 서강그라운드 [Java] https://www.acmicpc.net/problem/14938 1. 아이디어 각 지역까지의 최단 거리를 통해 아이템의 합을 구하는 문제로 다익스트라 알고리즘을 활용할 수 있고 N이 최대 100이어서 플로이드 워셜 알고리즘으로도 해결할 수 있다.2. 문제풀이 다익스트라 알고리즘은 1번 지역부터 N번까지 각 지역을 출발지로 설정한 후 아이템의 합을 구해보며 최댓값을 찾는 방식으로 구현했고, 플로이드 워셜 알고리즘은 2차원 dp 테이블을 순회하며 각 행을 출발지로 생각하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_Dijkstra { private static class Node implements Comparabl.. 2025. 2. 2. [백준] 11404번 - 플로이드 [Java] https://www.acmicpc.net/problem/11404 1. 아이디어 제목 그대로 플로이드 워셜 알고리즘을 활용하면 되며 플로이드 워셜 알고리즘에서 사용하는 dp 테이블을 출력하면 된다.2. 문제풀이 시작점과 도착점이 동일하면 0을 출력해야해서 dp 테이블 초기화 단계에서 0을 넣어줬고 시작점과 도착점이 동일한 경로가 여러 개 들어올 수 있어서 그 중 최솟값만 저장해야 했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final int INF = 1_000_000_000; public static void main(String[] args) throws IOException { .. 2025. 2. 2. [백준] 1389번 - 케빈 베이컨의 6단계 법칙 [Java] https://www.acmicpc.net/problem/1389 1. 아이디어 케빈 베이컨 수는 그래프에서 특정 노드와 다른 모든 노드와의 거리의 합과 같다. 각 사람에 대해 BFS 알고리즘으로 거리를 구해서 더하는 방식과 플로이드 워셜 알고리즘으로 거리 배열을 구해서 더하는 방법 두가지로 해결할 수 있었다.2. 문제풀이 - BFS친구관계가 중복으로 들어올 수 있어서 인접 리스트에 Set을 적용해서 중복을 제거하는 방식으로 구현했다. - 플로이드 워셜 알고리즘각 친구들과의 거리 정보를 담은 거리 배열을 생성한 후 각 행 또는 열의 합으로 케빈 베이컨 수를 간단하게 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { .. 2025. 1. 23. 이전 1 다음
