1956_운동 (60%대에서 자꾸 틀림)

사용 알고리즘: 플로이드 워셜

사용 언어: java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//dfs를 왜 돌리세요? 플로이드를 마치고 나면 `map[i][i]`에 들어가는게 i에서 출발해서 i로 끝나는 사이클의 최소 길이인데요.
//  ㄴ 헐 그렇네

public class Main_bj_1956_운동 {
    static int v,e;
//    static ArrayList<Edge>[] map;
    static int[][] map;
    static int answer = 400000;
    public static void main(String[] args) throws IOException {
        input();
        floydwasher();

//        for (int start = 1; start < v+1; start++) {
//            boolean[] visited = new boolean[v+1];
////            visited[start] = true;
//            for (int secondstart = 1; secondstart < v+1; secondstart++) { //dfs
//                if (map[start][secondstart] != 10001) {
//                    visited[secondstart] = true;
//                    makeLittleCircle(secondstart, start, map[start][secondstart], visited);
//                    Arrays.fill(visited, false);
//                }
//            }
//        }
        for (int i = 1; i < v+1; i++) {
            for (int j = 1; j < v+1; j++) {
                if(i == j) continue;
                else {
                    if (map[i][j] != 10001 && map[j][i] != 10001) //가는 길, 오늘 길 둘 다 있어야 함
                        answer = Math.min(answer, map[i][j] + map[j][i]); //갔으면 돌아오는 거까지 체크해야지~
                }
            }
        }

        //운동 경로를 찾는 것이 불가능한 경우에는 -1을 출력 -> 이거 빼먹음...
        if(answer == 400000) System.out.println(-1);
        else System.out.println(answer);
    }

    private static void makeLittleCircle(int secondstart, int end, int sum, boolean[] visited) {
        if (secondstart == end) {
            answer = Math.min(sum, answer);
//            System.out.println(answer);
        }

        for (int thirdstart = 1; thirdstart < v+1; thirdstart++) {
            if(!visited[thirdstart] && map[secondstart][thirdstart] != 10001) {
                visited[thirdstart] = true;
                makeLittleCircle(thirdstart, end, sum+map[secondstart][thirdstart], visited);
                visited[thirdstart] = false;
            }
        }

    }

    private static void floydwasher() { //연결에 연결 + 갈 수 있는 최소값 갱신
        for (int i = 1; i < v+1; i++) {
            for (int j = 1; j < v+1; j++) {
                for (int k = 1; k < v+1; k++) {
                    if(i!=j && map[i][k] + map[k][j] < map[i][j]) { //아!!! 최대+최대 = 오버플로우로 마이너스 됨
                        map[i][j] = map[i][k] + map[k][j];
                    }
                }
            }
        }

//        for (int i = 0; i < v+1; i++) {
//            System.out.println(Arrays.toString(map[i]));
//        }
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        map = new int[v+1][v+1];
//        Arrays.fill(map, Integer.MAX_VALUE); --> 2차원 배열은 이런 식으로 못 채운다
        for (int i = 0; i <= v; i++) {
            for (int j = 0; j <= v; j++) {
                map[i][j] = 10001;
            }
        }

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            map[start][end] = weight;
        }
    }

//    static class Edge {
//        int to;
//        int value;
//
//        public Edge(int to, int value) {
//            this.to = to;
//            this.value = value;
//        }
//    }
}

 

 

첫번째 틀림 -> Integer.MAX_VALUE 에 (+알파)가 되면 오버플로 때문에 -가 됨. 

                    -> 문제에서 최대 가중치는 10,000이라고 해서 Integer.MAX_VALUE가 아닌 적당한 값으로 바꿈

 

두번째 시간초과 -> dfs를 굳이 돌릴 필요가 없는데 돌림 (makeLittleCircle)

 

세번째 틀림 -> 가는 길이 있을 때, 무조건 더해버림(돌아오는 길이 없어서 max치를 찍어도) 

                    -> 가는 길이 있을 때 돌아오는 길도 있나 확인 후 더함

네번째 틀림 -> 문제에 조건으로 주어진 "길이 없으면 -1을 출력"을 빼먹음

 

===> 뭘 고쳐도 답이 안 나옴... 다른 블로그를 참고해봐도 로직이 같은데...

===> 플로이드 워셜에서 k를 for문 제일 밖에 둔 코드가 있어서 그렇게 바꿔봐도 똑같이 60%대에서 답이 안 나옴