import java.io.*;
class Station { //station 클래스 선언! (클래스와 객체 개념을 이용합니다..!)
String station_name; // 역이름
int station_num; // 역번호
Station(){
}
Station(int num, String name) { //Station의 생성자 메소드 선언.
station_num = num;
station_name = name;
}
}
class Subway{
String start_enter;
String end_enter;
static int start = 0;
static int end = 0;
}
public class test extends Subway { // 메인클래스..! subway 상속시키기!
public static void main(String [] args) {
Subway sb = new Subway();
int m = 10000; //null값 역할을 하는 m 선언
int s = 0,e = 0; //입력값 받아올 s,e
int i,j,k=0;
float min; //카운터 i,j,k 선언하기 for문에서 이용할 min값 사용 (= m값이 null값으로 쓸 쑤 잇게 하기..!)
int [] v = new int[40]; //v[]선언 하기. data배열에서 열이 계산 됫는지 안됫는지 유무 파악하는 기능 배열
float [] distance = new float[40]; //distance[]선언하기. 실제 거리 배열
int [] via = new int[40];
float [][] data = {
{0,2.5f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{2.5f,0,3.0f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,3.0f,0,6.6f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,6.6f,0,8.2f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,8.2f,0,1.6f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,1.6f,0,2.5f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,2.5f,0,3.0f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,3,0,2.3f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,2.3f,0,1.4f,1.6f,1.2f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,1.4f,0,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,1.6f,m,0,m,m,2.6f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,1.2f,m,m,0,m,m,3.0f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,0,2.2f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,2.6f,m,2.2f,0,1.4f,m,m,m,m,m,m,2.1f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,3.0f,m,1.4f,0,2.8f,m,m,m,m,m,m,2.4f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.8f,0,1.4f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.4f,0,1.5f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.5f,0,2.7f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.7f,0,1.0f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.0f,0,2.4f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.4f,0,m,m,m,m,m,m,m,m,m,m,0.6f,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,2.1f,m,m,m,m,m,m,m,0,m,m,2.1f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.4f,m,m,m,m,m,m,m,0,m,m,m,2.2f,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0,0.7f,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.7f,0,0.9f,m,m,m,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.1f,m,m,0.9f,0,0.8f,m,m,m,m,m,0.9f,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.2f,m,m,0.8f,0,1.8f,m,m,m,m,m,1.4f,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.8f,0,2.2f,m,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,2.2f,0,0.8f,m,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.8f,0,1.7f,m,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.7f,0,0.9f,m,m,m,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.6f,m,m,m,m,m,m,m,m,m,0.9f,0,m,m,m,m,m,m,m,0.7f},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.9f,m,m,m,m,m,m,0,m,0.9f,m,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.4f,m,m,m,m,m,m,0,m,0.8f,m,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.9f,m,0,m,1.0f,m,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.8f,m,0,m,0.8f,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.0f,m,0,2.6f,m,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.8f,2.6f,0,1.4f,m},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,1.4f,0,1.9f},
{m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,m,0.7f,m,m,m,m,m,m,1.9f,0},
};
String[] names = new String[40] ;
names[0] = "계양";
names[1] = "귤현";
names[2] = "박촌";
names[3] = "임학";
names[4] = "계산";
names[5] = "경인교대입구";
names[6] = "작전";
names[7] = "갈산";
names[8] = "부평구청";
names[9] = "부평시장";
names[10] = "부평";
names[11] = "동수";
names[12] = "부평삼거리";
names[13] = "간석오거리";
names[14] = "인천시청";
names[15] = "예술회관";
names[16] = "인천터미널";
names[17] = "문학경기장";
names[18] = "선학";
names[19] = "신연수";
names[20] = "원인재";
names[21] = "동춘";
names[22] = "동막";
names[23] = "일";
names[24] = "이";
names[25] = "삼";
names[26] = "사";
names[27] = "오";
names[28] = "육";
names[29] = "칠";
names[30] = "팔";
names[31] = "구";
names[32] = "십";
names[33] = "십일";
names[34] = "십이";
names[35] = "십삼";
names[36] = "십사";
names[37] = "십오";
names[38] = "십육";
names[39] = "십칠";
Station[] stations = new Station[40] ;
for(i=0;i<40;i++) {
stations[i] = new Station(i,names[i]); //http://ddogani.blog.me/50083572952 객체배열 감사합니다.
BufferedReader br = new BufferedReader( new InputStreamReader( System.in )); //bufferedReader 클래스의 사용.( 입력 스트림)
System.out.print(" 출발역을 입력하세욧! : ");
try {
sb.start_enter = br.readLine() ;
} catch (IOException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
for(i=0;i<40;i++) {
if(sb.start_enter.equals(stations[i].station_name)) {
start = i;
};
}
System.out.print(" 도착역을 입력하세욧! : ");
try {
sb.end_enter = br.readLine();
} catch (IOException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
for(j=0;j<40;j++) {
if(sb.end_enter.equals(stations[j].station_name)) {
end = j;
};
}
// start,end 값에 입력값 받기.
for( j=0; j<8; j++ ) {
v[j] = 0;
distance[j] = m;
} //초기화하기
distance[start] = 0; // 자기 자신과의 역거리는 0이므로 0으로 선언한다..!
for( i=0; i<8; i++ ) {
min = m;
for( j=0; j<8; j++ ) {
if( v[j] == 0 && distance[j] < min ) { //v[]의 역할은 그 열이 실행됬으면 다시하지 않는 역할.
k = j;
min = distance[j];
} //data[][] 에서 s지점 구하기.
} //distance가 s값을 받으면서 자기 자신의 위치 '0'을 사용 함으로써 자기 자신의 위치를 처음에
//
v[k] = 1; // 그래서 여기에 1을 넣어 줌으로써 안한 0 을 다시 for문 돌면서 처리 하는거지
if(min==m) break; //
for(j=0; j<8; j++) {
if(distance[j] > distance[k] + data[k][j]) { //data[k][j]의 의미는 k번 역에서 j번 역으로 가는 거리임...! 즉 distance[j]는 null값 역할을 하는
distance[j] = distance[k] + data[k][j]; via[j]=k; //m에 v[]값을 이용해 구해진 k열에그리고 ditance[k]는 0임 언제나..!자기자신임..!
} // s가 있는 행의 배열 구하기. distance[] s가 있는 행의 배열이 되는거지 //= 이말이 뭘 뜻하는 거냐면, 1번에서 갈 수 있는 역을 말하는 거지.
}
} // 이거 i있는 포문에 끝이여. i의 역할은 s역에서 ?역까지 반복문으로 다하 는거야 초기값은 위치찾고 다음에는 1역 2역...순서대로 찾는거지.
// 이 for문은 i가 7까지 돌면서 시작점에서 을 찾아서 넣고, v[]값을 이용해서 차례차례 그 열에 해당하는 distance를 구하는 방법...!
System.out.printf("n %d에서 출발하여, %d로 가는 최단 시간은 %d입니다.n", s, e, distance[e-1]);
int path[] = new int[40];
int path_cnt=0;
k=e-1;
while(true) { //무한 루프 선언.
path[path_cnt++]=k;
if(k==s-1)break; //끝점과 시작점이 같다면 필요없겟지.
k=via[k]; //via[]은 i를 받아오는 거잔아 거기 까지 몇번 돌았는지를 확인하는 배열이야.
}
System.out.print(" 경로는 : ");
for(i=path_cnt-1;i>=1;i--) {
System.out.printf("%d -> ",path[i]+1);
}
System.out.printf("%d입니다",path[i]+1);
}
}
}
|
