[UVA] 10099 The Tourist Guide
Posted 2008/05/04 00:36여행 가이드가 있다. 출발지부터 목적지까지 승객들을 대리고 가야하는데 길(Edge)마다 가중치만큼의 사람밖에 데려가지를 못한다. 그래서 한번에 모든 승객들을 데려가지 못하는 경우가 많다. 여행 가이드가 최소 몇번을 여행해야 하는가?
주의할점은 출발지부터 목적지까지 몇개의 Edge를 거쳐가든지 관계 없다는 것과 여행에는 항상 가이드가 함께가야만 한다는 점이다.
이 문제는 Prim 알고리즘을 통해서 해결할 수 있었다. 과거에 Prim알고리즘으로 코딩을 해봤던 것이 무척 도움이 됬다.
출발지부터 인접 Edge들을 우선순위 큐에 넣고 계속 가장 가중치가 큰 Edge들을 골라나간다. 그리고 목적지에 도착했을 때 정해진 Path(Edge)중에 가장 가중치가 낮은 Edge를 찾아 -1(가이드)을 해주고 승객의 숫자를 최소 가중치로 나눠주고 올림을 하면 그것이 정답이 된다.
//10099 The Tourist Guide
import java.util.PriorityQueue;
import java.util.Scanner;
/**
* Edge의 상태를 나타낸다.
*/
enum EdgeState {
WHITE, // 아직 한번도 사용되지 않은 Edge
GRAY, // 사용될 Edge의 후보군중에 원소
BLACK // 사용할 Edge의 집합군중에 원소
}
/**
* Edge를 나타내는 클래스이다.
*/
class Edge implements Comparable<Edge>{
int cityOfSource; // 시작 City
int cityOfDestination; // 목적지 City
int weight; // limit
@Override
public int compareTo(Edge arg0) {
return arg0.weight - weight;
}
}
public class Main {
Scanner in = new Scanner(System.in);
int nCity; // City의 개수
int nRoad; // Road(Edge)의 개수
int cityOfSource; // 출발할 도시
int cityOfDestination; // 목적지 도시
int nPassenger; // 승객의 수
int countOfScenario; // 시나리오의 번호
int[] parentOfCity; // City에 도착하기 바로 전의 City번호
int[][] matrixOfWeight; // Edge들의 limit를 나타내는 행렬
EdgeState[][] stateOfEdge; // Edge들의 상태 (WHITE, GRAY, BLACK)
PriorityQueue<Edge> priorityQueueOfEdge; // 인접 Edge들의 우선순위 큐
public
Main()
{
while(true) {
countOfScenario++;
init();
start();
print();
}
}
/**
* Standard out으로부터 입력받고 변수들을 초기화한다.
*/
private
void
init()
{
int tempCity1;
int tempCity2;
int tempWeight;
int i, j;
priorityQueueOfEdge = new PriorityQueue<Edge>();
nCity = in.nextInt();
nRoad = in.nextInt();
if(nCity == 0 && nRoad == 0)
System.exit(0);
parentOfCity = new int[nCity+1];
stateOfEdge = new EdgeState[nCity+1][nCity+1];
for(i=1 ; i<=nCity ; i++) {
for(j=1 ; j<=nCity ; j++) {
stateOfEdge[i][j] = EdgeState.WHITE;
}
}
matrixOfWeight = new int[nCity+1][nCity+1];
for(i=0 ; i<nRoad ; i++) {
tempCity1 = in.nextInt();
tempCity2 = in.nextInt();
tempWeight = in.nextInt();
matrixOfWeight[tempCity1][tempCity2] = tempWeight;
matrixOfWeight[tempCity2][tempCity1] = tempWeight;
}
cityOfSource = in.nextInt();
cityOfDestination = in.nextInt();
nPassenger = in.nextInt();
}
/**
* 초기화된 변수들로부터 해를 구한다.
*/
private
void
start()
{
int numberOfCity = cityOfSource;
Edge tempEdge = null;
while(numberOfCity != cityOfDestination) {
// 선택된 node의 frindge node를 우선순위 큐에 삽입
findEdges(numberOfCity);
// 우선순위 큐에서 가장 우선순위가 높은 Edge 추출
tempEdge = priorityQueueOfEdge.poll();
// parent정보 설정
if(parentOfCity[tempEdge.cityOfDestination] == 0) {
parentOfCity[tempEdge.cityOfDestination] = tempEdge.cityOfSource;
stateOfEdge[tempEdge.cityOfSource][tempEdge.cityOfDestination] = EdgeState.BLACK;
stateOfEdge[tempEdge.cityOfDestination][tempEdge.cityOfSource] = EdgeState.BLACK;
}
numberOfCity = tempEdge.cityOfDestination;
}
}
/**
* 최소 Trips를 찾아 출력한다.
*/
private
void
print()
{
int minimumWeight;
int nTrip;
// 선택된 경로 중 최소 가중치 판별
minimumWeight = findMinimumWeight(cityOfDestination) - 1;
nTrip = nPassenger / minimumWeight;
nPassenger %= minimumWeight;
nTrip = nPassenger>0 ? nTrip+1 : nTrip;
System.out.println("Scenario #" + countOfScenario);
System.out.println("Minimum Number of Trips = " + nTrip);
}
/**
* numberOfCity로부터 인접된 Edge들을 우선순위 큐에 넣는다.
* @param numberOfCity
*/
private
void
findEdges(
int numberOfCity
)
{
int i;
Edge tempEdge;
for(i=1 ; i<=nCity ; i++) {
if(matrixOfWeight[numberOfCity][i] > 0 &&
stateOfEdge[numberOfCity][i] == EdgeState.WHITE) {
tempEdge = new Edge();
tempEdge.cityOfSource = numberOfCity;
tempEdge.cityOfDestination = i;
tempEdge.weight = matrixOfWeight[numberOfCity][i];
priorityQueueOfEdge.add(tempEdge);
stateOfEdge[numberOfCity][i] = EdgeState.GRAY;
stateOfEdge[i][numberOfCity] = EdgeState.GRAY;
}
}
}
/**
* 완성된 Path중에서 최소 limit을 찾는다.
* @param numberOfCity
* @return
*/
private
int
findMinimumWeight(
int numberOfCity
)
{
if(parentOfCity[numberOfCity] == 0)
return Integer.MAX_VALUE;
int weight = matrixOfWeight[numberOfCity][parentOfCity[numberOfCity]];
int beforeWeight = findMinimumWeight(parentOfCity[numberOfCity]);
if(weight < beforeWeight)
return weight;
return beforeWeight;
}
public static void main(String[] args) {
new Main();
}
}
import java.util.PriorityQueue;
import java.util.Scanner;
/**
* Edge의 상태를 나타낸다.
*/
enum EdgeState {
WHITE, // 아직 한번도 사용되지 않은 Edge
GRAY, // 사용될 Edge의 후보군중에 원소
BLACK // 사용할 Edge의 집합군중에 원소
}
/**
* Edge를 나타내는 클래스이다.
*/
class Edge implements Comparable<Edge>{
int cityOfSource; // 시작 City
int cityOfDestination; // 목적지 City
int weight; // limit
@Override
public int compareTo(Edge arg0) {
return arg0.weight - weight;
}
}
public class Main {
Scanner in = new Scanner(System.in);
int nCity; // City의 개수
int nRoad; // Road(Edge)의 개수
int cityOfSource; // 출발할 도시
int cityOfDestination; // 목적지 도시
int nPassenger; // 승객의 수
int countOfScenario; // 시나리오의 번호
int[] parentOfCity; // City에 도착하기 바로 전의 City번호
int[][] matrixOfWeight; // Edge들의 limit를 나타내는 행렬
EdgeState[][] stateOfEdge; // Edge들의 상태 (WHITE, GRAY, BLACK)
PriorityQueue<Edge> priorityQueueOfEdge; // 인접 Edge들의 우선순위 큐
public
Main()
{
while(true) {
countOfScenario++;
init();
start();
print();
}
}
/**
* Standard out으로부터 입력받고 변수들을 초기화한다.
*/
private
void
init()
{
int tempCity1;
int tempCity2;
int tempWeight;
int i, j;
priorityQueueOfEdge = new PriorityQueue<Edge>();
nCity = in.nextInt();
nRoad = in.nextInt();
if(nCity == 0 && nRoad == 0)
System.exit(0);
parentOfCity = new int[nCity+1];
stateOfEdge = new EdgeState[nCity+1][nCity+1];
for(i=1 ; i<=nCity ; i++) {
for(j=1 ; j<=nCity ; j++) {
stateOfEdge[i][j] = EdgeState.WHITE;
}
}
matrixOfWeight = new int[nCity+1][nCity+1];
for(i=0 ; i<nRoad ; i++) {
tempCity1 = in.nextInt();
tempCity2 = in.nextInt();
tempWeight = in.nextInt();
matrixOfWeight[tempCity1][tempCity2] = tempWeight;
matrixOfWeight[tempCity2][tempCity1] = tempWeight;
}
cityOfSource = in.nextInt();
cityOfDestination = in.nextInt();
nPassenger = in.nextInt();
}
/**
* 초기화된 변수들로부터 해를 구한다.
*/
private
void
start()
{
int numberOfCity = cityOfSource;
Edge tempEdge = null;
while(numberOfCity != cityOfDestination) {
// 선택된 node의 frindge node를 우선순위 큐에 삽입
findEdges(numberOfCity);
// 우선순위 큐에서 가장 우선순위가 높은 Edge 추출
tempEdge = priorityQueueOfEdge.poll();
// parent정보 설정
if(parentOfCity[tempEdge.cityOfDestination] == 0) {
parentOfCity[tempEdge.cityOfDestination] = tempEdge.cityOfSource;
stateOfEdge[tempEdge.cityOfSource][tempEdge.cityOfDestination] = EdgeState.BLACK;
stateOfEdge[tempEdge.cityOfDestination][tempEdge.cityOfSource] = EdgeState.BLACK;
}
numberOfCity = tempEdge.cityOfDestination;
}
}
/**
* 최소 Trips를 찾아 출력한다.
*/
private
void
print()
{
int minimumWeight;
int nTrip;
// 선택된 경로 중 최소 가중치 판별
minimumWeight = findMinimumWeight(cityOfDestination) - 1;
nTrip = nPassenger / minimumWeight;
nPassenger %= minimumWeight;
nTrip = nPassenger>0 ? nTrip+1 : nTrip;
System.out.println("Scenario #" + countOfScenario);
System.out.println("Minimum Number of Trips = " + nTrip);
}
/**
* numberOfCity로부터 인접된 Edge들을 우선순위 큐에 넣는다.
* @param numberOfCity
*/
private
void
findEdges(
int numberOfCity
)
{
int i;
Edge tempEdge;
for(i=1 ; i<=nCity ; i++) {
if(matrixOfWeight[numberOfCity][i] > 0 &&
stateOfEdge[numberOfCity][i] == EdgeState.WHITE) {
tempEdge = new Edge();
tempEdge.cityOfSource = numberOfCity;
tempEdge.cityOfDestination = i;
tempEdge.weight = matrixOfWeight[numberOfCity][i];
priorityQueueOfEdge.add(tempEdge);
stateOfEdge[numberOfCity][i] = EdgeState.GRAY;
stateOfEdge[i][numberOfCity] = EdgeState.GRAY;
}
}
}
/**
* 완성된 Path중에서 최소 limit을 찾는다.
* @param numberOfCity
* @return
*/
private
int
findMinimumWeight(
int numberOfCity
)
{
if(parentOfCity[numberOfCity] == 0)
return Integer.MAX_VALUE;
int weight = matrixOfWeight[numberOfCity][parentOfCity[numberOfCity]];
int beforeWeight = findMinimumWeight(parentOfCity[numberOfCity]);
if(weight < beforeWeight)
return weight;
return beforeWeight;
}
public static void main(String[] args) {
new Main();
}
}
이올린에 북마크하기'C.S.E > Algorithm' 카테고리의 다른 글
| [IBM Developer Works]초보개발자 코드 트레이닝 Part 2. (0) | 2008/05/16 |
|---|---|
| [UVA] 10198 Counting (0) | 2008/05/06 |
| [UVA] 10099 The Tourist Guide (0) | 2008/05/04 |
| [UVA] 10183 How many Fibs? (0) | 2008/05/02 |
| [UVA] 10069 Distinct Subsequences (0) | 2008/05/01 |
| 자바 알고리즘 경진대회(JAC) 기대와 아쉬운점 (6) | 2008/04/18 |
