[Java] 백준 13168 내일로 여행 952hi의 접근방법

https://www.acmicpc.net/problem/13168

13168번: 내일로 여행

---

 

1. 접근방법

 

모든 경우의수를 돌면서 값을 구하는 알고리즘인 플로이드워샬을 사용해야겠다고 가장먼저 생각함

다익스트라로 사용해줄 수 있을것 같은데 모든 도시를 전부 한번씩 돌려주면 더 손해라고 생각해서 

플로이드 워샬을 사용하기로 생각했음.

 

문자열 -> 해쉬맵을 통해서 지역에 맞는 인덱스를 만들어서 3중배열의 인덱스로 사용해야겠다고 생각이듬

교통수단 문자열을 받아서 if문을 통해서 할인되는 교통수단이면 + 액션 아니면 그냥 리턴 방식 함수 필요

 

그 후 여행경로 별 인덱스를 통해 값 출력

2. 실수

 

이용 요금이 홀수 일때 2로나누어주면 내림처리가 되기때문에

홀수 *2는 짝수 / 짝수 * 2는 짝수 처럼 모든 값에 2를 처리해주는 방식으로 해결

 

문제를 잘못 읽어서 모든 도시를 줄때 이름이 같을 수 있다고 이해해서 시간이 좀걸렸다..

 

3. 느낀점

고민 조금 하고 플로이드 워샬 썻는데 글을 작성하면서 다익스트라로 했다면 결과가 어땠는지 궁금하다.

 

 

4. 코드

 

import java.io.*;
import java.util.*;
public class boj13168 {
	// boj13168
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stz.nextToken());
		int won = Integer.parseInt(stz.nextToken());
		Map<String, Integer> map = new HashMap<String, Integer>();
		stz = new StringTokenizer(br.readLine());
		String chk;
		
		//도시별 인덱스 생성
		for(int i=0;i<N;i++) {
			chk = stz.nextToken();
			map.put(chk, i);
		}
		int M = Integer.parseInt(br.readLine());
		int[] res = new int[M];
		stz = new StringTokenizer(br.readLine());
		// 여행경로 저장
		for(int i=0;i<M;i++) {
			chk = stz.nextToken();
			res[i] = map.get(chk);
		}
		
		int board[][][] = new int[N][N][2];//0 기본 1 내일로
		int t = Integer.parseInt(br.readLine());
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				// 모두 선택안된길 초기화 무한값쓰면 오버돼서 -1이 될수도 있어서 
				// 1000000으로 초기화
				board[i][j][0] = 1000000;
				board[i][j][1] = 1000000;
			}
		}
		
		String vehecle;
		int val,start,end,val2;
		
		for(int i=0;i<t;i++) {
			stz = new StringTokenizer(br.readLine());
			vehecle = stz.nextToken();
			start = map.get(stz.nextToken());
			end = map.get(stz.nextToken());
			val = Integer.parseInt(stz.nextToken());
			val2 = discount(val*2,vehecle);
			
			// 같은 도시 다른운송이용시 다른 가격일때 더 작은 것만
			if(board[start][end][0]>val*2) {
				board[start][end][0]=val*2;
				board[end][start][0]=val*2;
			}
			// 같은 도시 다른운송이용시 다른 가격일때 더 작은 것만
			if(board[start][end][1] > val2) {
				board[start][end][1] = val2;
				board[end][start][1] = val2;
			}
		}
		// 경출도 모든 경우의수 탐색 진행
		for(int k=0;k<N;k++) {
			for(int i=0;i<N;i++) {
				if(i==k) continue;
				for(int j=0;j<N;j++) {
					if(i==j || j==k) continue;
					if(board[i][j][0]>board[i][k][0]+board[k][j][0])
						board[i][j][0]=board[i][k][0]+board[k][j][0];
					if(board[i][j][1]>board[i][k][1]+board[k][j][1])
						board[i][j][1] = board[i][k][1]+board[k][j][1];
				}
			}
		}
		// one 기본가격
		// two 내일로 티켓사용시
		int one=0,two=won*2;
		for(int i=1;i<M;i++) {
			one += board[res[i-1]][res[i]][0];
			two += board[res[i-1]][res[i]][1];
		}
		if(one<=two) System.out.println("No");
		else System.out.println("Yes");
	}
	// 교통 수단별 할인 함수
	private static int discount(int val,String vehecle) {
		if(vehecle.equals("ITX-Saemaeul") || vehecle.equals("Mugunghwa") || vehecle.equals("ITX-Cheongchun")) return 0;
		else if(vehecle.equals("S-Train")|| vehecle.equals("V-Train") ) return val/2;
		return val;
	}
}

 

5. 결과