SWEA 5684. [Professional] 운동

1~N 번호로 이루어있는 N개의 건물이 있고 이 건물들을 잇는 시작점, 도착점, 거리 정보가 주어지는 M개의 일방통행 도로가 있어 시작점부터 시작해서 다시 시작점으로 돌아오는 사이클 중 가장 작은 사이클의 도로의 길이의 합을 구하는 문제이다. 최소 사이클을 찾기 위해 다익스트라 알고리즘을 이용하여 풀이하였다.

 

먼저, 도로의 정보를 Map에 저장한다.

Map<Integer, List<Road>> map = new HashMap<>();
for(int i=1; i<=n; i++) {
    map.put(i, new ArrayList<>());
}
for(int i=0; i<m; i++) {
    st = new StringTokenizer(br.readLine());
    int s = Integer.parseInt(st.nextToken()), e = Integer.parseInt(st.nextToken());
    int c = Integer.parseInt(st.nextToken());
    map.get(s).add(new Road(e, c));
}

 

 

시작점을 1부터 N까지 시작점으로 삼고 다익스트라 알고리즘을 적용하여 우선순위 큐에 도착점, 누적 이동 길이 정보를 가진 Road를 넣음으로서 이동하면서 가장 작은 사이클을 찾는다. 이미 방문했던 곳이라도 더 짧은 길이거나 시작점에 도착하는 길 이라면 그 길을 선택하여 해당 건물에 도착한다. 시작점에 도착하면 해당 방법이 시작점으로 돌아오는 가장 작은 사이클이 되며 누적된 도로 길이의 합을 업데이트해준다.

int min = Integer.MAX_VALUE;
for(int i=1; i<=n; i++) {
    PriorityQueue<Road> pq = new PriorityQueue<>(new Comparator<Road>() {
        @Override
        public int compare(Road o1, Road o2) {
            return o1.c - o2.c;
        }
    });
    int[] visited = new int[n+1];
    Arrays.fill(visited, Integer.MAX_VALUE);
    visited[i] = 0;
    for(Road next: map.get(i)) pq.add(new Road(next.e, next.c));
    while(!pq.isEmpty()) {
        Road current = pq.remove();
        if(current.e == i) {
            min = Math.min(min, current.c);
                break;
        }
        if(current.c > visited[current.e]) continue;
        visited[current.e] = current.c;
        for(Road next: map.get(current.e)) {
            if(visited[next.e] > current.c + next.c || next.e == i) {
                pq.add(new Road(next.e, current.c+ next.c));
            }
        }
    }
}
            
sb.append(min == Integer.MAX_VALUE ? -1 : min).append('\n');

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
            Map<Integer, List<Road>> map = new HashMap<>();
            for(int i=1; i<=n; i++) {
                map.put(i, new ArrayList<>());
            }
            for(int i=0; i<m; i++) {
                st = new StringTokenizer(br.readLine());
                int s = Integer.parseInt(st.nextToken()), e = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                map.get(s).add(new Road(e, c));
            }
            int min = Integer.MAX_VALUE;
            for(int i=1; i<=n; i++) {
                PriorityQueue<Road> pq = new PriorityQueue<>(new Comparator<Road>() {
                    @Override
                    public int compare(Road o1, Road o2) {
                        return o1.c - o2.c;
                    }
                });
                int[] visited = new int[n+1];
                Arrays.fill(visited, Integer.MAX_VALUE);
                visited[i] = 0;
                for(Road next: map.get(i)) pq.add(new Road(next.e, next.c));
                while(!pq.isEmpty()) {
                    Road current = pq.remove();
                    if(current.e == i) {
                        min = Math.min(min, current.c);
                        break;
                    }
                    if(current.c > visited[current.e]) continue;
                    visited[current.e] = current.c;
                    for(Road next: map.get(current.e)) {
                        if(visited[next.e] > current.c + next.c || next.e == i) {
                            pq.add(new Road(next.e, current.c+ next.c));
                        }
                    }
                }
            }
            
            sb.append(min == Integer.MAX_VALUE ? -1 : min).append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
    
    static class Road {
        int e, c;
        
        Road(int e, int c) {
            this.e = e;
            this.c = c;
        }
    }
}