도와주세요 메모리초과,, #13
Answered
by
YeonsangYoon
wjdgns7712
asked this question in
Q&A
도와주세요 메모리초과,,
#13
-
|
정말 정신이 혼미해지네요 각설하고 제 코드는 이렇습니다.. import java.io.*;
import java.util.*;
public class Main {
static Map<Integer, Integer>[] edges; // <K, V> edges[i] : i 번째 node에서 K번째 node로가는 edge의 weight
static ArrayList<Integer>[] parent; // <Int> parent[i] : i 번째 node로 최단거리로 가는 parent들의 배열
static int N, M, S, D;
static int[] dist; // dist[i] : S에서 i 번째 node로 가는 최단거리
static final int MAX = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
while(N!=0 && M!=0){
st = new StringTokenizer(br.readLine());
S = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
edges = new HashMap[N];
for (int i = 0; i < N; i++)
edges[i] = new HashMap<>();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int U = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());
edges[U].put(V, P);
}
// 여기까지는 그냥 입력받는거.
dijkstra(false); //최단경로 찾기
remove(D); // 최단경로 지우기
dijkstra(true); //최단거리 찾기
// 여기부터는 그냥 출력하는거.
bw.write(dist[D]!=MAX ? dist[D]+"\n" : "-1\n");
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
}
bw.flush();
bw.close();
br.close();
}
static void dijkstra(boolean flag){
dist = new int[N];
for (int i = 0; i < N; i++)
dist[i] = MAX;
dist[S] = 0; // S로부터 S를 제외하고 나머지 node까지의 거리를 모두 MAX값으로 초기화.
if (!flag) { // 처음시작하는 dijkstra면 최단경로를 위한 parent가 필요하니까 초기화해준다. 아니라면 굳이쓸필요없으니 초기화도 안한다.
parent = new ArrayList[N];
for (int i = 0; i < N; i++)
parent[i] = new ArrayList<>();
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[1]-b[1]); // <node_id, dist[i]> 에서 dist[i]에 대한 min heap
pq.add(new int[]{S, 0});
while(!pq.isEmpty()){
int[] tmp = pq.poll();
int now = tmp[0]; // 현재 node의 id
if (tmp[1] > dist[now]) // node[now]까지 오는 거리보다 edge의 weight가 더 크면 pass
continue;
for( Map.Entry<Integer, Integer> edge : edges[now].entrySet()){ // node[now]로 부터 출발하는 모든 edge에 대해서
int next = edge.getKey(); // edge가 향하는 node의 id
int cost = edge.getValue(); // edge의 weight
if (dist[now] + cost < dist[next]){ // next node까지 가는데 해당 edge를 사용했을때 더 빠르면?
dist[next] = dist[now] + cost; // 최솟값 갱신.
parent[next].clear(); // 해당 node로 가는 parent들 초기화.
parent[next].add(now); // next node의 parent로 now node 추가.
} else if (dist[now] + cost == dist[next]) // next node까지 가는데 해당 edge를 사용했을때 거리가 똑같다?
parent[next].add(now); // next node의 parent에 now node 추가. (최단경로가 여러개다.)
pq.add(new int[]{next, cost}); // pq에 새로운 edge 추가.
}
}
}
static void remove(int child){
if (child!=S) // child가 출발점이 아니라면
for(int p : parent[child]){ // child로 향하는 최단거리가 있는 모든 parent node에서
edges[p].remove(child); // parent -> child 로 향하는 edge를 지운다
remove(p); // 그리고 그 parent의 parent에도 반복적으로 수행해라.
}
}
}재귀호출은 remove함수 말고는 없는데... 도대체 어느부분에서 메모리가 터지는건지 모르겠네요. 개인적인 생각으로는 불필요한 변수도 최대한 줄였고해서 크게 문제될게 없어보이는데... 하루죙일 쳐다봐도 해결이 안되네요.. 도와주세요!ㅠ |
Beta Was this translation helpful? Give feedback.
Answered by
YeonsangYoon
Aug 16, 2021
Replies: 3 comments 4 replies
-
|
강사님 블로그 참고했는데, dijkstra 알고리즘 중 최단거리가 업데이트 될 때만 pq에 push하네요! |
Beta Was this translation helpful? Give feedback.
2 replies
-
|
우선 도움주셔서 감사합니다! |
Beta Was this translation helpful? Give feedback.
-
|
기존 다익스트라는 해당 정점으로 가는 최단거리가 갱신 될 때만 heap에 넣는 걸로 알고 있습니다. 근데 이 문제는 모든 최단 경로를 다 고려해야하기 때문에 == 상황도 고려해야 하는 것 같습니다! |
Beta Was this translation helpful? Give feedback.
-
|
해결은 하셨나요?? 저도 같은 문제를 풀다가 메모리 초과 때문에 고생을 좀 했습니다... 우선 저는 최단 경로를 역추적해서 지우는 과정을 bfs로 했는데 한 2시간 정도 고민하다가 동일한 정점일 계속 push하는 것 때문에 생기는 것을 확인 했습니다... 정훈님은 remove 함수를 dfs로 구현하셨는데 visited 배열을 하나 만들어서 동일 정점을 계속 호출하는 것을 한 번 막아보시는 게 어떨까요? |
Beta Was this translation helpful? Give feedback.
1 reply
-
|
동일 정점이 아니라 동일 간선이네요! 동일한 간선을 계속 호출하는 것을 방지 해야 합니다! |
Beta Was this translation helpful? Give feedback.
Answer selected by
wjdgns7712
-
import java.io.*;
import java.util.*;
public class Main {
static Map<Integer, Integer>[] edges; // <K, V> edges[i] : i 번째 node에서 K번째 node로가는 edge의 weight
static ArrayList<Integer>[] parent; // <Int> parent[i] : i 번째 node로 최단거리로 가는 parent들의 배열
static int N, M, S, D;
static int[] dist; // dist[i] : S에서 i 번째 node로 가는 최단거리
static final int MAX = Integer.MAX_VALUE;
static int [][] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
while(true){
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
if(N==0)
break;
st = new StringTokenizer(br.readLine());
S = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
edges = new HashMap[N];
for (int i = 0; i < N; i++)
edges[i] = new HashMap<>();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int U = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());
edges[U].put(V, P);
}
// 여기까지는 그냥 입력받는거.
dijkstra(false); //최단경로 찾기
visited = new int[501][501];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
visited[i][j]=0;
}
}
remove(D); // 최단경로 지우기
dijkstra(true); //최단거리 찾기
// 여기부터는 그냥 출력하는거.
bw.write(dist[D]!=MAX ? dist[D]+"\n" : "-1\n");
}
bw.flush();
bw.close();
br.close();
}
static void dijkstra(boolean flag){
dist = new int[N];
for (int i = 0; i < N; i++)
dist[i] = MAX;
dist[S] = 0; // S로부터 S를 제외하고 나머지 node까지의 거리를 모두 MAX값으로 초기화.
if (!flag) { // 처음시작하는 dijkstra면 최단경로를 위한 parent가 필요하니까 초기화해준다. 아니라면 굳이쓸필요없으니 초기화도 안한다.
parent = new ArrayList[N];
for (int i = 0; i < N; i++)
parent[i] = new ArrayList<>();
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[1]-b[1]); // <node_id, dist[i]> 에서 dist[i]에 대한 min heap
pq.add(new int[]{S, 0});
while(!pq.isEmpty()){
int[] tmp = pq.poll();
int now = tmp[0]; // 현재 node의 id
for( Map.Entry<Integer, Integer> edge : edges[now].entrySet()){ // node[now]로 부터 출발하는 모든 edge에 대해서
int next = edge.getKey(); // edge가 향하는 node의 id
int cost = edge.getValue(); // edge의 weight
if (dist[now] + cost < dist[next]){ // next node까지 가는데 해당 edge를 사용했을때 더 빠르면?
dist[next] = dist[now] + cost; // 최솟값 갱신.
pq.add(new int[]{next, dist[next]}); // pq에 새로운 edge 추가.
if(!flag){
parent[next].clear(); // 해당 node로 가는 parent들 초기화.
parent[next].add(now); // next node의 parent로 now node 추가.
}
} else if (dist[now] + cost == dist[next] && !flag){ // next node까지 가는데 해당 edge를 사용했을때 거리가 똑같다?
parent[next].add(now); // next node의 parent에 now node 추가. (최단경로가 여러개다.)
}
}
}
}
static void remove(int child){
if (child!=S) // child가 출발점이 아니라면
for(int p : parent[child]){ // child로 향하는 최단거리가 있는 모든 parent node에서
if(visited[child][p] == 1)
continue;
visited[child][p]=1;
edges[p].remove(child); // parent -> child 로 향하는 edge를 지운다
remove(p); // 그리고 그 parent의 parent에도 반복적으로 수행해라.
}
}
}이렇게 제출해서 맞았습니다! 틀린 부분이 크게 pq에 넣는 값과 조건이고 remove함수에서 visited 체크하는 부분이네요! |
Beta Was this translation helpful? Give feedback.
1 reply
-
|
와 저도 지금 보고 확인했는데 진짜네요... 거짓말처럼 통과되네요...ㅠㅠ 너무감사합니다! 진짜 상상도 못한 부분이네요... |
Beta Was this translation helpful? Give feedback.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
해결은 하셨나요??
저도 같은 문제를 풀다가 메모리 초과 때문에 고생을 좀 했습니다...
우선 저는 최단 경로를 역추적해서 지우는 과정을 bfs로 했는데 한 2시간 정도 고민하다가
동일한 정점일 계속 push하는 것 때문에 생기는 것을 확인 했습니다...
정훈님은 remove 함수를 dfs로 구현하셨는데 visited 배열을 하나 만들어서 동일 정점을 계속 호출하는 것을 한 번 막아보시는 게 어떨까요?