728x90
https://www.acmicpc.net/problem/21278
21278번: 호석이 두 마리 치킨
위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더
www.acmicpc.net
728x90
메모리: 17,748 KB , 시간: 252 ms
사용 알고리즘: 브루트포스 알고리즘, 플로이드-워셜, 최단 경로
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception{ final int MAX; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; // N := 건물의 개수, M := 도로의 개수 st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); MAX = N * M + 1; // 도로 정보 저장 int[][] edges = new int[N + 1][N + 1]; for (int i = 1; i <= N; i++) { Arrays.fill(edges[i], MAX); } // 도로 정보 입력 int A, B; for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); A = Integer.parseInt(st.nextToken()); B = Integer.parseInt(st.nextToken()); edges[A][B] = 1; edges[B][A] = 1; } // N이 100 이하이므로 플로이드-워셜로 각 도시에서 다른 도시로의 최단 거리 구하기 for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { for (int k = 1; k <= N; k++) { edges[j][k] = Math.min(edges[j][k], edges[j][i] + edges[i][k]); } } } // 두 가게를 조합하여 최단 거리 구하기 int building1 = 0, building2 = 0, sumOfDis = MAX * N, sum; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if(i == j) continue; // 같은 건물일 경우 넘어가기 sum = 0; for (int k = 1; k <= N; k++) { if(k == i || k == j) continue; // 치킨집일 경우 넘어가기 sum += Math.min(edges[k][i], edges[k][j]); } if(sum < sumOfDis) { building1 = i; building2 = j; sumOfDis = sum; } } } // 출력 // 왕복 거리이므로 최단 거리에 x2를 해줌 System.out.println(building1 + " " + building2 + " " + (sumOfDis * 2)); } }
728x90
'Problem Solving > BOJ' 카테고리의 다른 글
[백준, BOJ 15681] 트리와 쿼리 (java) (0) | 2023.12.23 |
---|---|
[백준, BOJ 2250] 트리의 높이와 너비 (java) (0) | 2023.12.23 |
[백준, BOJ 1025] 제곱수 찾기 (java) (1) | 2023.12.21 |
[백준, BOJ 1719] 택배 (java) (1) | 2023.12.20 |
[백준, BOJ 20440] 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 (java) (1) | 2023.12.18 |