[ 자바 ] - 방향 있는 최단거리

정말 많이나오는 문제인가보다 . 처음으로 어떤 회사 코테를 봤는데 최단거리문제가 나왔다.

최단거리 관련 공부를 전혀하지 않은입장에서 당연히 못풀었다.

 

그때 나온 문제는 시작점에서 목적지까지 갈때 최단거리를 구하는 방법이였는데 dfs방식을적용했더니 ㅋㅋ 최단거리를 못찾앗다.

 

일단 최단거리 문제 유형이 여러가지인데 , 이 문제는 단방향으로 가는 최단거리이다

 

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

1753번: 최단경로

 

 

다른거 참고안하고 혼자 짜본로직...이다 . 결과는 메모리 초과.. 발생 

 

문제의 유형은 

 

정점, 간선 , 시작점을 주고 각 간선의 가중치를 제공해준다 

 

ex )

1 에서 2로 갈때 가중치 2

1 에서 3로 갈때 가중치 3

2 에서 4 로 갈때 가중치 1

3 에서 4로 갈때 가중치 1

등등

 

이차 배열은 만들고 각각의 좌표에 가중치를 넣었다 

ex) arr[1][2] = 2  ,arr[1][3] = 3 ,arr[2][4] = 1 ,  arr[3][4] = 1

 

그리고 시작점에서부터 이어지는 정점을 체크할 boolean 배열과 가중치를 담을 int배열을 만들었다

이렇게 해서 만약 arr[1][2]=2 일경우 boolean[2] =true ,  int[2] = 2을 담아 비교했다

 

마지막으로4는  1에서는 연결이 안됬지만  boolean배열에서 1과 연결된 2,3을 찾아 가중치를 계산하여 더작은 수를 저장하도록 하였다. 이렇게 할 경우 단방양의 문제는 찾을수 있엇지만 앞에서 말한바와같이 메모리 초과가 발생한다 

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {

static int count=0;
public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int v = sc.nextInt();
int e = sc.nextInt();

int vlength=v+1; 

int s = sc.nextInt();

int[][] map = new int[vlength][vlength];

boolean[] check = new boolean[vlength];
int[] result = new int[vlength];


for(int i = 0;i<e;i++) {
int x = sc.nextInt();
int y = sc.nextInt();
int z = sc.nextInt();
map[x][y]=z;

}
Arrays.fill(result, Integer.MAX_VALUE);


for(int i=1;i<vlength;i++) {
for(int j=1;j<vlength;j++) {
if(i==1 && map[i][j]>0) {
check[j]=true;
result[j]=map[i][j];
} 

if(check[i]&&i>1) {
if(map[i][j]!=0) {

if(result[j]>map[i][j]+result[i]) {
result[j]=map[i][j]+result[i];
check[j]=true;
}

}
}
}
}

for(int i=1;i<vlength;i++) {
if(i==1) {
System.out.println(0);
}else if(i==Integer.MAX_VALUE) {
System.out.println("INF");
}else {
System.out.println(result[i]);
}

}
    }
}

 

 

 

다음은 우선순위큐를 사용한 방법이다.

다른분의 문제 푸는 방법을 찾아봤고 그중에서 내가 위에서 사용했던 방법과 가장 비슷한 콛드를 찾아 디버깅을 돌려보면서 이해를 했다.

 

edge라는 class를 만들고 인터페이스 Comparable 을 추가해주어야한다. 우선순위 큐에서 더낮은 edge를 꺼내기 위함이다

 

edge란 클래스는 목적지와 가중치를 저장해 놓을 것이다 

 

(scanner 보다 bufferreader가 30배?가까이 더 빠르다고하여 사용하였다.--> 계속 시간 초과가 뜨기때문에 이제부터는 이걸사용할것이다) 

 

node가 들어갈 arraylist 리스트를 생성하고 정점 수만큼 배열을 생성한다.

 

각 배열에는 시작점 기준으로 넣을 것이다

ex) 5 1 1 이면 배열5번에 edge(목적지 1, 가중치 1) 이 들어간다 ==> 단방향 

 

그담에는 위에서처럼 각 목적지마다의 최단거리와 체크를 할 int,boolean 배열을 생성한다. 여기서 낮은 우선순위를 찾기때문에 int배열에는 Integer.MaxValue를 넣어준다 , 21억 ... 얼마가 들어갈것이다. (int 범위가 +21~-21억까지인걸로 기억한다 ) 

 

그리고 다익스트라 메소드를 생성한다

 

메소드 안에는 시작점부터 각 지점간의 거리를 구하는 방식을 구한다

 

이 메소드에서는 우선순위 큐를 일반 큐와 달리 weight을 기준으로 weight 이 낮은 순서부터 진행한다 ( comparable 때문에 ) 

 

처음 1.0을 큐에 넣고  큐에서 하나를 꺼낸다. (  1,0을 넣은 이유는 시작점이 1이기때문에 1에서 1을깔때 최소거리는 0이기 떄문 , 만약 1에서 1갈때 가중치가 있다면, 1,가중치를 넣으면됨 )

 

꺼낸 값을 edge에 넣으면 목적지는 1, 가중치는 0 이되고 0은 int 배열 1번과 비교하여 작을 경우 int배열 1번에 넣는다

 

이제 맨처음만든 Arraylist<Edge>[1]을 가져와 반복문을 돌리고 , 그 안에 들어있는 edge들을 꺼내 목적지에 가중치를 비교하여 적은 경우 넣고 , 이어지는 다음 목적지를 우선순위 큐에 넣는다.

 

결과적으로 시작점에서 다음지점까지의 최단거리를 우선순위 큐에 넣고 , int[] 배열과 비교하는 방식이다.  

 

import java.io.*;
import java.util.*;



public class Main {
static ArrayList<Edge>[] arr ;
static int[] checkArr ;
static boolean[] bool;
static int MAX = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(br.readLine());
int length = V+1;
arr =new ArrayList[length];
for(int i=0;i<length;i++) {
arr[i]=new ArrayList<Edge>();
}
checkArr=new int[length];
bool = new boolean[length];
for(int i = 0;i<E;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
arr[a].add(new Edge(b,c));
}

check(start);
for(int i =1 ;i < length;i++) {
if(checkArr[i]==MAX) System.out.println("INF");
else System.out.println(checkArr[i]);
}


}

static void check(int start) {
Arrays.fill(checkArr, MAX);
checkArr[start]=0;
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.add(new Edge(start,0));
while(!pq.isEmpty()) {
Edge e =  pq.poll();
int dest1 = e.dest;
int weight1 = e.weight;
if(bool[dest1]) continue;
else bool[dest1]=true;


for(int i =0 ; i< arr[dest1].size();i++) {
Edge e2= arr[dest1].get(i);
int dest2 = e2.dest;
int weight2 =e2.weight+weight1;
if(checkArr[dest2]>weight2)
checkArr[dest2]=weight2;
pq.add(new Edge(dest2,weight2));

}
}

}


}
class Edge implements Comparable<Edge> {
int dest;
int weight;
Edge(int dest,int weight){
this.dest=dest;
this.weight=weight;
}
@Override
public int compareTo(Edge o) {
// TODO Auto-generated method stub
return Integer.compare(this.weight, o.weight);
}
}

<참고>

https://velog.io/@lre12/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Dijkstra-Algorithm

다익스트라 알고리즘(Dijkstra Algorithm)