[ 자바 ] 경로찾기 & 최단거리 - 1

백준 1753번과 최단거리를 구하는 prirority queue를 사용하여  예시 문제는 풀었지만 , 제출 한 결과 8%에서 메모리 초과가 발생하였다.

 

 

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

1504번: 특정한 최단 경로

 

내가 풀려고 했던 방식은 시작점부터  모든 경로를 하나씩 탐색하는데 , priority queue를 사용하여 거리가 낮은거 우선으로 꺼내서 탐색하는 방식이다.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
static ArrayList<Edge>[] arr;
static int count;
static int mustP1;
static int mustP2;
static int start;

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int e  =Integer.parseInt(st.nextToken());
 start = 1;

arr = new ArrayList[n+1];
for(int i=0;i<n+1;i++) {
arr[i]=new ArrayList<>();
}

for(int i=0;i<e;i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());

arr[s].add(new Edge(d,w,0,false,false));
arr[d].add(new Edge(s,w,0,false,false));
}

st = new StringTokenizer(br.readLine());
mustP1=  Integer.parseInt(st.nextToken());
mustP2 =  Integer.parseInt(st.nextToken());

 count = bfs();
 System.out.println(count);
}

static int bfs() {
PriorityQueue<Edge> q = new PriorityQueue<Edge>();
q.add(new Edge(start,0,0,false,false));

while(!q.isEmpty()){
Edge e = q.poll();
int count = e.count;
boolean two = e.destionation==mustP1?true:e.two;
boolean three=e.destionation==mustP2?true:e.three;
if(e.destionation==4) {
if(two&&three) {
return e.count;
}
}
for(int i =0;i<arr[e.destionation].size();i++) {
Edge tmp = arr[e.destionation].get(i);
q.add(new Edge(tmp.destionation,tmp.weight,count+tmp.weight,two,three));
}
}
q.clear();
return -1;

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


}

 

 

 

정답을 찾지못하여 다른분은 어떤방식으로 찾았는지 찾아보게되었다.

다들 다익스트라를 사용하였지만 반드시 지나야하는점을 중점으로 계산하는 방식을 사용하였다.

 

그래서 코드를 수정했는데 똑같이 메모리 부족이 발생하였다. 코드가 더 간결하고 쉽게 변했는데..

 

전체경로를 못찾는 경우 처리와 무작정 큐에 쌓는 부분이 문제가되는것같다 . 내일은 다른사람이 푼 코드를보고 보완해야겟다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
static ArrayList<Edge>[] arr;
static int count;
static int mustP1;
static int mustP2;
static int start;
static int n;

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
 n = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
start = 1;

arr = new ArrayList[n + 1];
for (int i = 0; i < n + 1; i++) {
arr[i] = new ArrayList<>();
}

for (int i = 0; i < e; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());

arr[s].add(new Edge(d, w));
arr[d].add(new Edge(s, w));
}

st = new StringTokenizer(br.readLine());
mustP1 = Integer.parseInt(st.nextToken());
mustP2 = Integer.parseInt(st.nextToken());

//start -> mustP1 ->mustP2 -> end (n)

//start -> mustP2 ->mustP1 -> end (n)

int case1 = dijkstra(start,mustP1);
case1+= dijkstra(mustP1,mustP2);
case1+= dijkstra(mustP2,n);

int case2 = dijkstra(start,mustP2);
case2+= dijkstra(mustP2,mustP1);
case2+= dijkstra(mustP1,n);
if(case1>=case2) System.out.println(case2);
else  System.out.println(case1);

}
static int dijkstra(int start,int end) {
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.add(new Edge(start,0));
while(!pq.isEmpty()) {
Edge e = pq.poll();
int dest = e.dest;
int curCount = e.weight;

if(dest==end) {
return curCount;
}

for(int i=0;i<arr[dest].size();i++) {
Edge ee = arr[dest].get(i);
pq.add(new Edge(ee.dest,curCount+ee.weight));
}

}

return -1;
}

}

class Edge implements Comparable<Edge> {
int weight;
int dest;

Edge(int destination,int weight){
this.dest=destination;
this.weight=weight;
}

@Override
public int compareTo(Edge o) {
// TODO Auto-generated method stub
return Integer.compare(weight,o.weight);
}
}