[백준 / BOJ] 20183 골목 대장 호석 - 효율성 2 (Java)

문제

출처 : https://www.acmicpc.net/problem/20183

20183번: 골목 대장 호석 - 효율성 2

교차로 N개 교차로를 잇는 골목 M개(단, 골목에는 통행료가 존재한다.)가 주어진다. 

A교차로에서 B교차로로 갈때, 이 경로의 통행료 합을 C 이하로 만드는 경로중 통행료의 최댓값을 최소로 하는 경로를 구하는 문제다 

---

풀이

전형적인 다익스트라 알고리즘으로 풀리는 문제였다.

알고리즘은 다익스트라를 사용하면 풀리기때문에 따로 설명할게 없고, 최소힙에 들어갈 자료구조를 적절히 구현해주면 된다.

문제에서 원하는게 "시작지점 A에서 도착지점 B로 갈때의 최대 통행료" 와 "시작지점 A에서 도착지점 B로 갈때의 누적 통행료"니 자료구조또한 위와 같이 만들고, 누적 통행료보다는 최대 통행료를 최소로 만드는것이 더 중요하기 때문에 우선 최대 통행료가 작은 순서로 최소힙에 넣어주고, 최대 통행료가 같다면, 누적통행료가 작은 순서로 최소힙에 넣어줬다.

(누적 통행료가 더 작은걸 넣어도 항상 손해보는일이 없음)

 

주요 소스코드

1. 자료구조

	private static class Position implements Comparable<Position>{
		
		int idx;
		long maxWeight, sumWeight;
		
		public Position(int idx, long maxWeight, long sumWeight){
			this.idx = idx;
			this.maxWeight = maxWeight;
			this.sumWeight = sumWeight;
		}
		
		@Override
		public int compareTo(Position position){
			if(this.maxWeight > position.maxWeight) return 1;
			if(this.maxWeight < position.maxWeight) return -1;
			if(this.maxWeight == position.maxWeight){
				if(this.sumWeight > position.sumWeight) return 1;
				if(this.sumWeight < position.sumWeight) return -1;
			}
			return 0;
		}
		
	}

2. 다익스트라

	private long findMinShame(){
		PriorityQueue<Position> pq = new PriorityQueue<Position>();
		pq.add(new Position(this.startNode, 0, 0));
		long[] check = new long[this.node+1];
		for(int i = 0; i <= this.node; i++) check[i] = 9223372036854775800L;
		while(!pq.isEmpty()){
			Position position = pq.poll();
			if(position.maxWeight >= check[position.idx]) continue;
			if(position.idx == this.endNode) return position.maxWeight;
			check[position.idx] = position.maxWeight;
			List<Street> nowStreets = this.streets.get(position.idx);
			for(int i = 0; i < nowStreets.size(); i++){
				Street nextStreet = nowStreets.get(i);
				int nextIdx = nextStreet.to;
				long nextMaxWeight = max(position.maxWeight, nextStreet.money);
				long nextSumWeight = position.sumWeight + nextStreet.money;
				if(check[nextIdx] <= nextMaxWeight || nextSumWeight > this.money) continue;
				Position nextPosition = new Position(nextIdx, nextMaxWeight, nextSumWeight);
				pq.add(nextPosition);
			}
		}
		return -1;
	}

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/20183%20%EA%B3%A8%EB%AA%A9%20%EB%8C%80%EC%9E%A5%20%ED%98%B8%EC%84%9D%20-%20%ED%9A%A8%EC%9C%A8%EC%84%B1%202/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃