[Codeground] 연습문제 할인권

- 문제 : https://www.codeground.org/practice/practiceProblemView (codeground에 로그인 해야지 열람 가능합니다.)

 최소 비용을 찾는 문제입니다. 전체 경로와 각 경로마다 비용과 할인권이 주어집니다. 시작 위치에서 도착 위치까지 이동하는 모든 경로 중, 가장 비용이 적게 드는 경로에서 지불해야하는 비용이 할인권보다 많으면 할인권을 구매합니다. P(1 <= P <= 10000)개의 시작 위치와 도착 위치에서 경로를 확인해 할인권을 몇개 구매해야하는지 구하는 문제 입니다.

- 풀이

 모든 경로를 확인하기 위해 DFS를 사용했습니다. A에서 B까지 가는 경로가 주어지고 그 중간에 수많은 경유지가 있을 경우 모든 경유지를 확인하도록 했습니다. 처음에는 간단하게 현재 이동 가능한 경로 중에 가장 비용이 적은 곳을 가려고 했습니다. 그러나 돌아갈때 비용이 덜 드는 경우가 있을 수 있기 때문에 가능한 모든 경로를 확인하도록 했습니다. 알고리즘의 효율성을 높이기 위해 경로를 찾으면서 목적지에 도착 했을때 최소 비용을 계속해서 갱신해줬습니다. 그리고 경로를 찾는 과정에서 목적지에 도착하기도 전에 최소 비용을 넘는 경우에는 해당 경로의 탐색을 멈추도록 했습니다.

- 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class DiscountTicket {

	BufferedReader br;
	int[][] map, routeInfo, myRoute;
	boolean[][] check;
	int testCaseNum;
	int stationNum, routeNum, discountTicketPrice, myRouteNum;
	int totalPrice, ticketCount;
	int minPrice;

	void solve() {
		String[] str;
		int row, col, price;
		br = new BufferedReader(new InputStreamReader(System.in));

		try {
			testCaseNum = Integer.parseInt(br.readLine());
			for (int i = 0; i < testCaseNum; i++) {
				str = br.readLine().split(" ");
				stationNum = Integer.parseInt(str[0]);
				routeNum = Integer.parseInt(str[1]);
				discountTicketPrice = Integer.parseInt(str[2]);
				map = new int[stationNum + 1][stationNum + 1];
				check = new boolean[stationNum + 1][stationNum + 1];

				for (int j = 1; j <= routeNum; j++) {
					str = br.readLine().split(" ");
					row = Integer.parseInt(str[0]);
					col = Integer.parseInt(str[1]);
					price = Integer.parseInt(str[2]);
					map[row][col] = map[col][row] = price;
				}

				myRouteNum = Integer.parseInt(br.readLine());
				myRoute = new int[myRouteNum][2];
				for (int j = 0; j < myRouteNum; j++) {
					str = br.readLine().split(" ");
					row = Integer.parseInt(str[0]);
					col = Integer.parseInt(str[1]);
					myRoute[j][0] = row;
					myRoute[j][1] = col;
				}

				//DFS 시작
				for (int route = 0; route < myRouteNum; route++) {
					minPrice = 999999;
					checkGoal(myRoute[route][0], myRoute[route][1], myRoute[route][0]);
					if (minPrice > discountTicketPrice) {
						ticketCount++;
					}
					totalPrice = 0;
					minPrice = 999999;
				}
				System.out.println("Case #"+(i+1));
				System.out.println(ticketCount);
				ticketCount = 0;
			}

		} catch (NumberFormatException | IOException e) {
			e.printStackTrace();
		}
	}

	void checkGoal(int startPoint, int endPoint, int nowPoint) {
		for (int next = 1; next <= stationNum; next++) {
			if (check[nowPoint][next] == true || map[nowPoint][next] == 0) {
				continue;
			}

			// 경로를 탐색하며 축적된 totalPrice가 현재까지 경로를 탐색하며 갱신된 비용의 최소값보다 크면
			// 해당 경로를 더 이상 탐색하지 않는다.
			// 경로의 최소값을 찾아서 할인권과 가격을 비교하는 문제인데 최소값보다 큰 값은 더 이상 계산할 의미가 없다.
			if (minPrice < totalPrice) {
				return;
			}

			if (next == endPoint) {
				totalPrice += map[nowPoint][next];
				if (minPrice > totalPrice) {
					minPrice = totalPrice;
				}
				totalPrice -= map[nowPoint][next];
				continue;
			}

			if ((map[nowPoint][next] + totalPrice) < discountTicketPrice) {
				check[nowPoint][next] = true;
				check[next][nowPoint] = true;
				totalPrice += map[nowPoint][next];

				checkGoal(startPoint, endPoint, next);

				check[nowPoint][next] = false;
				check[next][nowPoint] = false;
				totalPrice -= map[nowPoint][next];
			}
		}
	}

	public static void main(String[] args) {
		DiscountTicket m = new DiscountTicket();
		m.solve();
	}

}