https://www.acmicpc.net/problem/1956
1956번: 운동
첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의
www.acmicpc.net
1956, 운동 📌 난이도 : Gold 4
📌 알고리즘 : 플로이드 와샬 (Floyd-Warshall)
이번 문제도 플로이드 와샬을 통한 최단 거리를 구하는 문제이다.
📚 Process 초기화 및 선언 : 마을의 개수 V, 도로의 개수 E 를 입력받고 E개만큼 단방향 그래프를 생성해준다. 양방향이 아님에 주의해야 한다.
추가로 여기서 연결되는 노드가 없을 때는 INF 로 초기화 해준다.
public static void input() throws IOException{
StringTokenizer st;
st = new StringTokenizer(br.readLine(), " ");
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
graph = new int[V+1][V+1];
// init
// INF 는 해당 노드에서 연결되는 노드가 없음을 의미
// 자신에서 자신은 0
for(int i=1; i<=V; i++) {
for(int j=1; j<=V; j++) {
if (i != j) {
graph[i][j] = INF;
}
}
}
while(E-- >0) {
st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
graph[a][b] = c;
}
}
: 여기서 3중 루프를 통한 플로이드 와샬을 사용하여 최단거리를 초기화한다.
여기서 주의할 점은 i 와 k 가 같은 경우, 자기 자신임을 의미하기 때문에 예외처리 해준다.
플로이드 와샬을 통한 최단 거리 초기화가 종료되면 자기 자신을 제외한 두 정점을 조회한다.
두 정점의 값이 INF 가 아니면 (연결되는 노드가 있음) 사이클이 존재한다는 의미이다.
ans 에 최솟값을 갱신해주며 탐색을 종료한다.
public static void pro() {
// 플로이드 와샬
for(int i=1; i<=V; i++) {
for(int j=1; j<=V; j++) {
for(int k=1; k<=V; k++) {
// jl -> lk = jk 이기 때문에 자기 자신임을 의미
if(j==k) continue;
// 최단거리 초기화
if(graph[j][k] > graph[j][i] + graph[i][k]) {
graph[j][k] = graph[j][i] + graph[i][k];
}
}
}
}
ans = INF;
for(int i=1; i<=V; i++) {
for(int j=1; j<=V; j++) {
// 자기 자신을 제외한 두 정점이
if(i == j) continue;
// 서로에게 가는 경로가 있다면 사이클이 존재한다는 뜻!
if(graph[i][j] != INF && graph[j][i] != INF) {
ans = Math.min(ans, graph[i][j] + graph[j][i]);
}
}
}
ans = (ans == INF) ? -1 : ans;
System.out.println(ans);
}
✅ 전체 코드 import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int V, E, ans;
static int INF = 987654321;
static int[][] graph;
public static void main(String[] args) throws IOException{
input();
pro();
}
public static void input() throws IOException{
StringTokenizer st;
st = new StringTokenizer(br.readLine(), " ");
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
graph = new int[V+1][V+1];
// init
// INF 는 해당 노드에서 연결되는 노드가 없음을 의미
// 자신에서 자신은 0
for(int i=1; i<=V; i++) {
for(int j=1; j<=V; j++) {
if (i != j) {
graph[i][j] = INF;
}
}
}
while(E-- >0) {
st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
graph[a][b] = c;
}
}
public static void pro() {
// 플로이드 와샬
for(int i=1; i<=V; i++) {
for(int j=1; j<=V; j++) {
for(int k=1; k<=V; k++) {
// jl -> lk = jk 이기 때문에 자기 자신임을 의미
if(j==k) continue;
// 최단거리 초기화
if(graph[j][k] > graph[j][i] + graph[i][k]) {
graph[j][k] = graph[j][i] + graph[i][k];
}
}
}
}
ans = INF;
for(int i=1; i<=V; i++) {
for(int j=1; j<=V; j++) {
// 자기 자신을 제외한 두 정점이
if(i == j) continue;
// 서로에게 가는 경로가 있다면 사이클이 존재한다는 뜻!
if(graph[i][j] != INF && graph[j][i] != INF) {
ans = Math.min(ans, graph[i][j] + graph[j][i]);
}
}
}
ans = (ans == INF) ? -1 : ans;
System.out.println(ans);
}
}