[백준] no1865:웜홀 - 벨만포드 알고리즘

문제

Input

1번째 줄 : 테스트 케이스의 수
2번째 줄 : 지점(Node)수 도로(Edge)수 웜홀(wormhole)수
3번째 줄 ~ 도로수+웜홀수 : 시작지점 도착지점 비용

1번째 줄을 제외하고 테스트케이스만큼 2~3번 반복

* 단, 도로는 무방향, 웜홀은 단방향

Output

YES : 테스트 케이스 내에서, 출발지점에서 다시 출발지점으로 도착했을 때 시간 역행이 가능한 케이스가 있는 경우
NO : 불가능한 경우

문제 링크 : https://www.acmicpc.net/problem/1865

---

원리

벨만포드 알고리즘 : 음수를 포함한 최단거리 구하는 알고리즘

 

* 처음 나의 시도 : 비슷한 논리이지만, 이중배열을 이용한 BFS 탐색의 경우 소모되는 메모리가 너무 심하다.

1. 이중배열을 이용해 도로를 양방향 비용체크

2. 웜홀이 있는 경우, 이중 배열 내에서 해당 방향 도로의 비용을 -값으로 업데이트

3. BFS를 이용해 탐색(모든 경로를 파악)

   (* 가령, 빙 돌아가더라도 -값이 되는 경우가 있다면 YES임)

4. 탐색중 비용이 -가 되는 경우가 있다면 탐색 종료 후 YES

5. 모든 탐색이 끝나고 아무런 경우가 없다면 NO

---

학습 내용 - 벨만포드 vs 다익스트라

: 최단거리를 구할 대 주로 사용되는 대표적인 두 알고리즘이다.

다익스트라	매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다. * 다익스트라는 방문하지 않은 노드 중에서 최단 거리가 가장 가까운 노드만을 방문한다.
벨만포드	(정점 - 1)번의 매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다. * 다익스트라와 차이점은 매 반복마다 모든 간선을 확인한다는 것이다.

---

나의 코드

[실패]  시도1. BFS를 이용한 탐색 - 실패원인 : BFS 연산이 너무 많음

1. 입력을 통해 맵 초기화

2. BFS를 이용한 이중배열 내 이동한 경로 탐색

3. 탐색 중 처음 출발지점과 같은곳에 도착하면 합계를 보고 음수면 시간역행한 경우이므로 YES, 양수면 NO

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int T, Node, Edge, WH;
    private static StringTokenizer st, tempSt;
    private static int[][] map;
    private static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());

        for(int i=0; i<T ; i++) {
            Search();
        }

        bw.close();
    }


    private static void Search() throws IOException {
        st = new StringTokenizer(br.readLine());
        Node = Integer.parseInt(st.nextToken());
        Edge = Integer.parseInt(st.nextToken());
        WH = Integer.parseInt(st.nextToken());

        map = new int[Node+1][Node+1];
        initialize();

        System.out.println("initializing");

        for(int i=1 ; i<=Node ; i++) {
            BFS(i);
        }

    }

    private static void initialize() throws IOException {
        for(int i = 0 ; i < Edge ; i++) {
            tempSt = new StringTokenizer(br.readLine());
            int departure = Integer.parseInt(tempSt.nextToken());
            int arrival = Integer.parseInt(tempSt.nextToken());
            int cost = Integer.parseInt(tempSt.nextToken());
            map[departure][arrival] = map[arrival][departure] = cost;
        }
        for(int i = 0 ; i < WH ; i++) {
            tempSt = new StringTokenizer(br.readLine());
            int departure = Integer.parseInt(tempSt.nextToken());
            int arrival = Integer.parseInt(tempSt.nextToken());
            int cost = Integer.parseInt(tempSt.nextToken()) * -1;
            map[departure][arrival] = cost;
        }
    }

    /**
     * 이니셜라이징은 문제 X
     * BFS가 문제
     */
    private static void BFS(int start) throws IOException {
        Deque<Move> dq = new ArrayDeque<>();
        visited = new boolean[Node+1][Node+1];
        visited[start][start] = true;
        dq.add(new Move(start, 0));
        boolean YorN = false;
        /**
         * 1. DFS를 이용해 출발 노드로부터 출발노드로 도착하는 경우 탐색
         * 2. 도착하면 재귀종료
         * 3. 만약 중간에 -값 나오면 재귀 종료 후 cost 반환
         * 4.
         */
        while(!dq.isEmpty()) {
            Move now = dq.poll();
            if(now.town == start) {
                // 출발점에 도달한 뒤 시간역행한 경우
                if (now.sum < 0) YorN = true;
                // 출발지점에 돌아왔으나 시간역행은 실패한 경우는 별다른 처리 없음
                // 출발지점에 도착만 했다면 break;
                break;
            }

            for(int next = 1 ; next <= Node ; next++) {
                if(map[now.town][next]==0) continue;
                if(!visited[now.town][next]) {
                    visited[now.town][next] = true;
                    dq.add(new Move(next, now.sum + map[now.town][next]));
                }
            }
        }

        if (YorN) bw.write("YES\n");
        else bw.write("NO\n");
    }

    private static class Move {
        private int town, sum;
        public Move(int town, int sum) {
            this.town = town;
            this.sum = sum;
        }
    }

[실패] 시도2. 벨만포드 알고리즘 적용 중 : 인덱스 설정 실수 (이 부분으로 이틀이나 헤맴...)

마지막에 인덱스 범위를 잘못 잡아 오류발생 (백준 제출 후 32%에서 오류 발생시, 이 부분을 확인해보자)

잘못된 범위

        for(int i = 0; i < Node; i++) {
            if(bellmanFord(i)) {  // 벨만포드 확인 후 minusCircle이 가능하다면,
                isMinusCircle = true;  // 아래 NO가 입력되는 부분을 제껴주기 위함
                bw.write("YES\n"); // YES입력 후 더이상 구할 필요 없으니 break;
                break;
            }
        }

 

올바른 범위

        for(int i = 1; i <= Node; i++) {
            if(bellmanFord(i)) {  // 벨만포드 확인 후 minusCircle이 가능하다면,
                isMinusCircle = true;  // 아래 NO가 입력되는 부분을 제껴주기 위함
                bw.write("YES\n"); // YES입력 후 더이상 구할 필요 없으니 break;
                break;
            }
        }

 

[성공] 시도3. 벨만포드 알고리즘 적용

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int T, Node, Edge, WH;
    private static int INF = Integer.MAX_VALUE;
    private static StringTokenizer st, tempSt;
    private static int[] dist;
    private static ArrayList<ArrayList<Move>> map;

    public static void main(String[] args) throws IOException {
        // 각 테스트 케이스를 반복 실행
        T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) Search();
        bw.flush();
        bw.close();
        br.close();
    }

    /**
     * 실제 각 테스트 케이스를 구하는 메소드
     */
    private static void Search() throws IOException {
        st = new StringTokenizer(br.readLine());
        Node = Integer.parseInt(st.nextToken());
        Edge = Integer.parseInt(st.nextToken());
        WH = Integer.parseInt(st.nextToken());
        dist = new int[Node + 1];// start에서 출발하여 각 노드에 도착하는 최단거리를 업데이트하며 기록해줄 배열

        map = new ArrayList<>();
        for (int i = 0; i <= Node; i++) map.add(new ArrayList<>());

        initialize();

        boolean isMinusCircle = false; // 벨만포드에 아무것도 성립하지 않는 경우 체크용

        for(int i = 1; i <= Node; i++) {
            if(bellmanFord(i)) {  // 벨만포드 확인 후 minusCircle이 가능하다면,
                isMinusCircle = true;  // 아래 NO가 입력되는 부분을 제껴주기 위함
                bw.write("YES\n"); // YES입력 후 더이상 구할 필요 없으니 break;
                break;
            }
        }

        if(!isMinusCircle) bw.write("NO\n");
    }

    /**
     * 각 테스트케이스별 입력을 초기화해주는 메소드
     */
    private static void initialize() throws IOException {
        for (int i = 0; i < Edge; i++) {
            tempSt = new StringTokenizer(br.readLine());
            int departure = Integer.parseInt(tempSt.nextToken());
            int arrival = Integer.parseInt(tempSt.nextToken());
            int cost = Integer.parseInt(tempSt.nextToken());

            map.get(departure).add(new Move(arrival, cost));
            map.get(arrival).add(new Move(departure, cost));
        }
        for (int i = 0; i < WH; i++) {
            tempSt = new StringTokenizer(br.readLine());
            int departure = Integer.parseInt(tempSt.nextToken());
            int arrival = Integer.parseInt(tempSt.nextToken());
            int cost = Integer.parseInt(tempSt.nextToken()) * -1;
            map.get(departure).add(new Move(arrival, cost));
        }
    }

    private static boolean bellmanFord(int start) {
        Arrays.fill(dist, INF); // start에서 출발하여 각 노드에 도착하는 최단거리를 업데이트하며 기록해줄 배열
        dist[start] = 0; // 시작점 초기화
        boolean update = false; // 최단거리가 업데이트 되는지 확인용

        // (정점의 개수 - 1)번 동안 최단거리 초기화 작업을 반복
        for(int i=1; i<Node ; i++) {
            update = false;

            for(int j=1 ; j<=Node ; j++) {
                for(Move move : map.get(j)) {
                    // INF가 아닌 경우를 충족시키기 위해 시작점을 0으로 초기화 한 것
                    // 기존에 저장된 최단거리보다, j번째에서 해당지점으로 새로이동하는 경우가 더 최단거리일 경우 작은값으로 업데이트
                    if(dist[j] != INF && dist[move.town] > dist[j] + move.sum) {
                        dist[move.town] = dist[j] + move.sum;
                        update = true;
                    }
                }
            }

            // 더이상 최단거리 업데이트가 이루어지지 않는 경우 멈춤
            if(!update) break;
        }

        if(update) {
            for(int i=1 ; i<=Node ; i++) { // 1 ~ Node번까지 모든 노드를 체크하기 위함
                for(Move move : map.get(i)) {
                    if(dist[i] != INF && dist[move.town] > dist[i] + move.sum) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    /**
     * 탐색을 위한 객체 클래스
     */
    private static class Move {
        private int town, sum;

        public Move(int town, int sum) {
            this.town = town;
            this.sum = sum;
        }
    }

 

---

레퍼런스

참고링크 : https://steady-coding.tistory.com/91

다익스트라 vs 벨만포드 알고리즘 비교 정리 참고글 : kdb.velog