[백준, JAVA]1800번, 인터넷 설치

문제 링크

1800번: 인터넷 설치

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이분 탐색

오름차순으로 정렬된 값들에서 특정한 값을 찾는 과정입니다.

중간 값을 임의의 값으로 설정하여 찾는 값과 비교하여 동일하면 찾는 값이 되고 크면 시작값이 임의의 값이 되고 작으면 최대값이 임의의 값이 되어 그 과정을 반복하여 찾는 값이 정렬된 값에 존재하는지 확인하는 방법입니다.

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

BFS

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심

1. K개의 인터넷 선은 무료로 설치가 가능하다.

2. 1번에서 N까지 연결하는 최소 지불 비용을 출력한다.

3. 지불 비용은 무료로 설치된 인터넷 선을 제외한 가장 비싼 비용이다.

4. N까지 연결할 때 다른 번호와는 연결되지 않아도 상관없다.

 

 

이분 탐색으로 지불 비용을 구해서 BFS탐색을 진행하여 해당 지불 비용이 만족하면서 1 -> N번까지 도착하는지 확인합니다.

 

이후 이분 탐색으로 값을 줄이거나 증가시켜서 최소 지불 비용을 구해서 결과로 출력하였습니다.

 

※BFS 탐색을 진행시 저는 다익스트라 알고리즘으로 구현하였습니다.

 

예제입력 1.

비용의 최대값 : 9

 

이분 탐색으로 중간값(지불 비용) 구하기

start : 0

end : 9

(0 + 9) / 2 = 4

 

1 -> N 연결하는 BFS탐색 시작!

 

BFS탐색시 1에서 N을 갈 때 가중치가 지불 비용보다 큰 개수를 구해서 탐색이 끝난 뒤 N번에 도착했을 때 지불 비용보다 큰 인터넷 선이 K보다 많을 경우 해당 지불 금액은 불가능하다고 판단하였습니다.

 

지불 비용 4에서 BFS 탐색으로 N까지 경로를 살펴보면

 

1 -> 3 -> 2 -> 5

 

이 경로에서 지불 비용(4)보다 큰 인터넷 선은 1개(2 -> 5)

K=1로써 해당 인터넷 선 비용은 내지 않아도 됩니다.

 

지불 비용(4)보다 큰 인터넷 선이 제거되었기 때문에 해당 지불 비용으로 인터넷을 연결할 수 있습니다.

 

다시 중간값 구하기

※최소 지불 비용을 구하는 것이기 때문에 BFS 탐색으로 중간값 지불 비용이 만족하면 중간값을 줄이는 방식으로 이분 탐색을 진행합니다.

start : 0

end : 3

(0 + 3) / 2 = 1

 

 

지불 비용 1에서 BFS 탐색으로 N까지 경로를 살펴보면

 

1 -> 2 - > 5

이 경로에서 지불 비용(4)보다 큰 인터넷 선은 2개(1->2, 2->5)

K=1로써 지불 비용 1보다 더 큰 지불을 해야하기 때문에 해당 지불 비용(1)은 불가능

 

다시 중간값 구하기

start : 2

end : 3

(2 + 3) / 2 = 2

 

지불 비용 2에서 BFS 탐색으로 N까지 경로를 살펴보면

 

1 -> 2 - > 5

이 경로에서 지불 비용(2)보다 큰 인터넷 선은 2개(1->2, 2->5)

K=1로써 지불 비용 2보다 더 큰 지불을 해야하기 때문에 해당 지불 비용(2)은 불가능

 

다시 중간값 구하기

start : 3

end : 3

(3 + 3) / 2 = 3

 

지불 비용 3에서 BFS 탐색으로 N까지 경로를 살펴보면

 

1 -> 2 - > 5

이 경로에서 지불 비용(3)보다 큰 인터넷 선은 2개(1->2, 2->5)

K=1로써 지불 비용 3보다 더 큰 지불을 해야하기 때문에 해당 지불 비용(3)은 불가능

 

다시 중간값 구하기

start : 4

end : 3

 

이분 탐색에서 시작 값이 끝의 값보다 커지면 탐색 종료로써 여기서 탐색을 종료합니다.

 

지금까지 만족한 지불 비용의 최소값 4을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• String.charAt()을 이용해서 N, P, K, 그래프의 값을 나누었습니다.
• 이분 탐색으로 중간값(지불 비용)을 구하였습니다.
• 지불 비용으로 1->N번까지 연결이 가능하는지 확인하는 bfs함수를 실행하였습니다.
• 연결 가능시 최소 지불 비용, 연결 불가능시 -1을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs는 다익스트라 알고리즘으로 PriorityQueue<>()를 사용하여 BFS 탐색을 진행하는 함수입니다.
• bfs는 받은 지불 비용이 1 -> N번 까지 연결가능하는지 확인하는 BFS 탐색 함수입니다.

 

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

public class Main {
	//다익스트라 BFS탐색에서 PriorityQueue에 사용되는 클래스
    static class cable implements Comparable<cable>{
        int next, value;
        public cable(int next, int value) {
            this.next = next;
            this.value = value;
        }

        @Override
        public int compareTo(cable o) {
            return this.value - o.value;
        }
    }
    static int N,P,K;
    static ArrayList<ArrayList<cable>> line = new ArrayList<>();	//그래프 저장 리스트
    static int[] dis;		//지불 비용보다 큰 인터넷 선 연결되는 횟수 저장하는 배열
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        dis = new int[N+1];

        for(int i=0;i<=N;i++)
            line.add(new ArrayList<>());

        int end = Integer.MIN_VALUE;
        int start = 0;
        //그래프 정보 저장 및 지불 비용 최대값 구하기
        for(int i=0;i<P;i++){
            st = new StringTokenizer(br.readLine()," ");
            int cur = Integer.parseInt(st.nextToken());
            int next = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            end = Math.max(end,value);
            line.get(cur).add(new cable(next,value));
            line.get(next).add(new cable(cur,value));
        }

        int answer = Integer.MIN_VALUE;
        //이분 탐색으로 중간값(지불 비용)기준 BFS탐색
        while(start<=end){
            int mid = (start + end)/2;
            if(bfs(mid)){
                answer = mid;
                end = mid-1;
            }else
                start = mid+1;
        }
        //이분 탐색 후 만족하는 지불 비용값이 없는 경우
        if(answer == Integer.MIN_VALUE)
            bw.write("-1");
        else		//지불 비용 존재시 최소값
            bw.write(answer + "");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //다익스트라 BFS 탐색으로 지불 비용에 만족하도록 1 -> N이 가능하는지 확인하는 함수
    static boolean bfs(int mid){
        PriorityQueue<cable> pq = new PriorityQueue<>();
        pq.add(new cable(1, 0));
        Arrays.fill(dis,Integer.MAX_VALUE);
        dis[1] = 0;
        while(!pq.isEmpty()){
            cable cur = pq.poll();
            int curNode = cur.next;
            int value = cur.value;
            if(dis[curNode] < value)
                continue;
            for(cable next : line.get(curNode)){
                int nextValue = value;
                if(next.value > mid)
                    nextValue++;
                if(nextValue < dis[next.next]){
                    dis[next.next] = nextValue;
                    pq.add(new cable(next.next,nextValue));
                }
            }
        }
        //K번 이하로 지불 비용보다 큰 인터넷 선 확인
        return dis[N]<=K;
    }
}