[백준, Java] 1939번, 중량제한(다익스트라)

문제 링크

1939번: 중량제한

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

이 문제에 핵심

1. N개의 섬이 존재하며, 몇 개의 섬 사이에는 다리가 설치되어 있고 차들이 지나다닐 수 있습니다.

2. 다리에는 중량 제한이 존재합니다.

3. 시작 섬 공장에서 도착 섬 공장까지 물건을 옮길 수 있는 최대값을 결과로 출력합니다.

4. 입력값의 두 섬은 항상 연결하는 경로가 존재합니다.

5. 두 섬 사이에는 여러 다리가 중복되어 존재할 수 있습니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 다익스트라를 통해서 실을 수 있는 최대값을 탐색합니다.

 

3. 탐색을 통해 얻은 최대값을 결과로 출력합니다.

 

 

다익스트라 탐색

 

각 섬과 도로를 기준으로 양방향 그래프을 만들 수 있습니다.

 

이후, 시작 섬부터 다익스트라 탐색을 진행합니다.

 

다익스트라 탐색을 진행하는 조건은

 

지나온 다리의 중량 제한의 최소값이 가장 큰 값부터 탐색을 진행합니다.

 

※ 예제입력 과정을 살펴보시면 이해하시기 편하실 것입니다.

 

중복된 다리

 

중복된 다리가 존재할 때는 중량 제한이 더 큰 다리만 이용하도록 설정합니다.

 

다리의 중량제한을 저는 Map<Integer, Map<Integer, Integer>> 을 통해서 관리하였습니다.

 

해석하면

 

 Map<출발지,  Map< 도착지, 중량제한>>입니다.

 

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 3

 

M : 3

 

 

다리 및 섬을 통한 그래프 형성

 

시작 섬 : 1

 

도착 섬 : 3

 

 

 

 

2. 다익스트라를 통해서 실을 수 있는 최대값을 탐색합니다.

 

시작 섬부터 다익스트라 탐색을 진행합니다.

 

 

 

출발 섬 1번부터 시작해서 다리를 통해 인접한 섬 접근

 

2번째 섬 : 최소 중량제한 = 2

 

3번째 섬 : 최소 중량제한 = 3

 

최소 중량 제한이 더 큰 3번째 섬을 탐색합니다.

목적지에 도착했으므로 탐색을 종료합니다.

 

 

3. 탐색을 통해 얻은 최대값을 결과로 출력합니다.

 

다익스트라로 얻은 최소 중량제한 = 최대 물품수

 

최소 중량 제한 : 3

 

3을 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 다리 및 섬의 정보를 띄어쓰기 기준 나누었습니다.
• Map<Integer, Map<Integer, Integer>>을 통해 다리의 중량제한을 저장합니다.
• search함수를 통해서 다익스트라 탐색을 통해 시작섬에서 도착섬까지 최소 중량을 구합니다.
• 탐색이 끝난 뒤 최소 중량값(=최대 물품수)을 결과로 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 최소 중량제한을 기준으로 내림차순으로 다익스트라를 진행합니다.

결과코드

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


public class Main {
    //다익스트라 탐색할 때 사용할 inner Class
    static class Info implements Comparable<Info>{
        //현재 위치
        int pos;
        //최소 중량제한
        int minWeight;
        public Info(int pos, int minWeight){
            this.pos = pos;
            this.minWeight = minWeight;
        }
        //최소 중량 제한 기준 내림차순 정렬
        @Override
        public int compareTo(Info o) {
            return o.minWeight - this.minWeight;
        }
    }

    //다리 연결 정보 저장 리스트
    static List<List<Integer>> bridges = new ArrayList<>();
    //다리 중량 제한 정보 저장 Map
    static Map<Integer, Map<Integer, Integer>> weights = new HashMap<>();
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        //다리 연결 정보 리스트 초기화
        for(int i=0;i<=N;i++){
            bridges.add(new ArrayList<>());
        }
        //입력값 저장
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine()," ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            //중복되는 다리일 때
            if(weights.containsKey(start) && weights.get(start).containsKey(end)) {
                //중량 제한 더 큰 값으로 변경
                weights.get(start).put(end, Math.max(weights.get(start).get(end), weight));
                weights.get(end).put(start, Math.max(weights.get(end).get(start), weight));
            }else{		//중복된 다리가 아닐 때
                bridges.get(start).add(end);
                bridges.get(end).add(start);
                //해당 섬에서 출발한 적이 없을 때
                if(!weights.containsKey(start)){
                    weights.put(start, new HashMap<>());
                }
                if(!weights.containsKey(end)){
                    weights.put(end, new HashMap<>());
                }
                //중량 제한 설정
                weights.get(start).put(end, weight);
                weights.get(end).put(start, weight);
            }
        }
        //시작 및 도착 섬 입력값 저장
        st = new StringTokenizer(br.readLine()," ");
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        //다익스트라 탐색 진행
        int result = search(start, end, N);
        //옮기는 최대 물품 수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        //결과 출력
        bw.flush();
        bw.close();
        br.close();
    }
    //다익스트라 탐색을 통해 최소 중량제한을 구하는 함수
    static int search(int start, int end, int N){
        //다익스트라에 사용할 우선순위 큐
        PriorityQueue<Info> pq = new PriorityQueue<>();
        //그래프 탐색에 사용할 방문 여부 확인 배열
        boolean[] visited = new boolean[N+1];
        //시작 섬 우선순위 큐에 저장
        pq.add(new Info(start, Integer.MAX_VALUE));
        //다익스트라 탐색 진행
        while(!pq.isEmpty()){
            Info info = pq.poll();
            //도착섬에 왔을 때
            if(info.pos == end){
                return info.minWeight;
            }
            //현재 섬이 이미 방문한 섬일 때
            if(visited[info.pos]){
                continue;
            }
            //현재 섬 방문으로 변경
            visited[info.pos] = true;
            //인접한 다리를 기준으로 탐색 진행
            for(Integer nxt : bridges.get(info.pos)){
                //방문하지 않은 섬일 때
                if(!visited[nxt]){
                    //최소 중량제한으로 비교하여 우선순위 큐에 저장
                    pq.add(new Info(nxt, Math.min(info.minWeight, weights.get(info.pos).get(nxt))));
                }
            }
        }
        return 0;
    }
}