[백준 JAVA] 2307 도로검문

2307 도로검문

https://www.acmicpc.net/problem/2307

문제설명

그래프의 노드와 간선으로 구성된 도로망에서 특정 두 노드(1번 노드와 N번 노드) 간의 경로를 찾고

그 경로의 최소 거리와, 해당 경로의 간선 하나를 제외했을 때의 최대 거리 차이를 계산한.

문제풀이

• 최소 거리 계산:
  • 다익스트라 알고리즘을 사용하여 1번 노드에서 N번 노드까지의 최소 거리를 계산한다.
  • 이 과정에서 각 노드에 대한 최단 경로를 기록하는 배열 path를 유지한다.
• 최대 거리 계산:
  • 최소 거리로 도달한 경로를 따라 각 간선을 하나씩 제거하면서 다시 최단 경로를 계산한다.
  • 이때 간선을 제거한 후의 경로에서의 거리 값을 비교하여 최대 거리를 찾는다.
• 결과 출력:
  • 최대 거리에서 최소 거리를 빼고 그 결과를 출력한다.
  • 만약 최종 최대 거리 값이 무한대라면, 도달할 수 없으므로 -1을 출력한다.

O(n log⁡ n)   시간복잡도

 

• 다익스트라 알고리즘:
  • 다익스트라 알고리즘의 시간 복잡도는 O((N+M)log⁡N)가 소요된다.
  • 여기서 N은 노드의 수, M은 간선의 수이다.
• 최대 거리 계산:
  • 각 간선을 하나씩 제거하고 그에 대해 다시 다익스트라 알고리즘을 실행하므로
  • 이 단계의 시간 복잡도는 O(M×(N+M)log⁡N)이다.
• 전체 시간 복잡도:
  • 따라서 전체 시간 복잡도는 O((N+M)log⁡N+M×(N+M)log⁡N)이다.

 

전체코드

import java.util.*;
import java.io.*;

public class Main {
    public static boolean[] prime; // 소수 여부를 저장할 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int M = Integer.parseInt(st.nextToken()); // 범위의 시작 숫자
        int N = Integer.parseInt(st.nextToken()); // 범위의 끝 숫자

        // N까지의 소수 여부를 추적하기 위한 prime 배열 초기화
        prime = new boolean[N + 1]; // 0부터 N까지, 총 N+1개의 요소
        get_prime(); // 소수 배열을 채우는 메서드 호출

        StringBuilder sb = new StringBuilder();

        // M부터 N까지 범위를 반복
        for (int i = M; i <= N; i++) {
            // 현재 숫자가 소수로 표시되지 않으면 StringBuilder에 추가
            if (!prime[i]) sb.append(i).append('\n'); // 소수인 숫자 뒤에 줄 바꿈을 추가
        }

        // 지정된 범위 내의 모든 소수 출력
        System.out.println(sb);
    }

    // 에라토스테네스의 체 알고리즘을 사용하여 소수 배열을 채우는 메서드
    public static void get_prime() {
        // 0과 1은 소수가 아니므로 false로 설정
        prime[0] = prime[1] = true;

        // 최대 숫자의 제곱근까지 반복
        for (int i = 2; i <= Math.sqrt(prime.length); i++) {
            // 이미 소수로 표시된 경우
            if (prime[i]) continue;

            // i의 배수를 소수가 아니라고 표시 (i*i부터 시작)
            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = true; // 소수가 아님을 표시
            }
        }
    }
}