[백준, DP, JAVA] P.1753 최단 경로

 

처음에는 2차원 배열에 맵을 담아서 방향 그래프를 따른 우선 순위큐 기반의 다익스트라를 구현하였습니다.(여기까지는 스스로 아이디어 생각해내서 하루종일 걸려서 구현까지 했지만...

import java.util.*;

public class Main {
	static int V,E;
	
	public static void main(String[] args ) {
		Scanner scr = new Scanner(System.in);
		final int INF = 10000;
		
		V = scr.nextInt();
		E = scr.nextInt();
		int startV = scr.nextInt();
		
		int[][] map = new int[V+1][V+1];
		int[] result = new int[V+1];
		
		for(int i=1;i<=V;i++) {
			for(int j=1;j<=V;j++) {
				if(i == j) {
					map[i][j] = 0;
					continue;
				}
				map[i][j] = INF;
			}
			
			result[i] = INF;
		}
		
		for(int i=0;i<E;i++) {
			int u = scr.nextInt();
			int v = scr.nextInt();
			int w = scr.nextInt();
			
			map[u][v] = w;
		}
		
		PriorityQueue<Vertax> pq = new PriorityQueue<Vertax>((Vertax v1, Vertax v2) -> {
			return v1.w - v2.w;
		});
		
		Vertax vertax = new Vertax(startV,0);
		pq.add(vertax);
		result[startV] = 0;
		
		
		while(!pq.isEmpty()) {
			Vertax v = pq.poll();
			
			for(int i=1;i<=V;i++) {
				if(map[v.u][i] == 0 || map[v.u][i] == INF) {
					continue;
				}
				
				if(v.w + map[v.u][i] < result[i]) {
					result[i] = v.w + map[v.u][i];
					pq.add(new Vertax(i,result[i]));
				}
			}
		}
		
		StringBuffer sb = new StringBuffer();
		for(int i=1;i<=V;i++) {
			sb.append(result[i] == INF? "INF\n" : String.valueOf(result[i]) + "\n");
		}
		
		System.out.println(sb.toString());
	}
	
}

class Vertax {
	int u,v,w;
	
	public Vertax(int u, int w) {
		this.u = u;
		this.w = w;
	}
}

하지만 메모리 초과가 떠버리더군요;;;

그래서 질문 검색을 보니 방향 그래프이기 때문에 방향에 해당하지 않는 곳까지 배열에 불필요하게 할당을 하다보니 메모리 낭비가 많이 되는것 같습니다. 그래서 2차원 배열을 넣어두고 정점과 간선을 따로 객체화해서 필요한 정점과 간선만 활용하도록 구현하기로 했습니다.

package 그래프이론.p1753최단경로.newtype;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	public static int V,E,START;
	public static boolean[] isVisited;
//	public static int[] wList;
	public static int INF = 1000000000;
	
	public static void main(String[] args) {
		Scanner scr = new Scanner(System.in);
		
		int u,v,w;
		V = scr.nextInt();
		E = scr.nextInt();
		START = scr.nextInt();
		isVisited = new boolean[V+1];
		List<Vertax> vList = new ArrayList<>();
		
		for(int i=0;i<=V;i++) {
			vList.add(new Vertax(i));
		}
		
		for(int i=1;i<=E;i++) {
			u = scr.nextInt();
			v = scr.nextInt();
			w = scr.nextInt();
			
			vList.get(u).edges.add(new Edge(v,w));
		}
		
		Vertax startV = vList.get(START);
		startV.w = 0;
		PriorityQueue<Vertax> pq = new PriorityQueue<>((Vertax v1, Vertax v2) -> {
			if(v1.w > v2.w) {
				return 1;
			}else if(v1.w < v2.w) {
				return -1;
			}else {
				if(v1.id > v2.id) {
					return 1;
				}else if (v1.id < v2.id) {
					return -1;
				}else {
					return 0;
				}
			}
		});
		
		pq.add(startV);
		
		while(!pq.isEmpty()) {
			Vertax vertax = pq.poll();
//			System.out.println("start: " + vertax.id);
			if(vertax.isVisited) {
				continue;
			}
			
			vertax.isVisited = true;
			
			for(Edge edge : vertax.edges) {
//				System.out.println("from: " + vertax.id + " to: " + edge.to + " w: " + wList[edge.to]);
//				System.out.println("v.w: " + vertax.w + " edge.w: " + edge.w);
				if(vertax.w + edge.w < vList.get(edge.to).w) {
					vList.get(edge.to).w = vertax.w + edge.w;
					
					if(!vList.get(edge.to).isVisited) {
						pq.add(vList.get(edge.to));
					}else {
						vList.get(edge.to).isVisited = false;
						pq.add(vList.get(edge.to));
					}
					
//					System.out.println("from: " + vertax.id + " to: " + edge.to + " w: " + vList.get(edge.to).w);
//					System.out.println("v.id: " + vertax.id + " v.w: " + vertax.w + " edge.w: " + edge.w);
				}
			}
		}
		
		for(int i=1;i<vList.size();i++) {
			int value = vList.get(i).w;
			
			if(value == INF) {
				System.out.println("INF");
			} else {
				System.out.println(vList.get(i).w);
			}
		}
	}
}

class Vertax {
	int id;
	List<Edge> edges = new ArrayList<Edge>();
	boolean isVisited = false;
	int w;
	
	public Vertax(int id) {
		this.id = id;
		w = 1000000000;
	}
}

class Edge {
	int to;
	int w;
	
	public Edge(int to, int w) {
		this.to = to;
		this.w = w;
	}
}

여기까지 구현하면서 문제를 제대로 읽지 않아서 하루종일 삽질을 한 부분이 있습니다. 바로 
[서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.] 이 문구입니다. 저는 당연히 각 정점 사이에 간선은 하나만 있는 것으로 가정하고 문제를 풀었습니다. 그래서 while문 안에 for문을 처음에는 

	for(Edge edge : vertax.edges) {
				if(vertax.w + edge.w < vList.get(edge.to).w) {
					vList.get(edge.to).w = vertax.w + edge.w;
					pq.add(vList.get(edge.to));
					
			}
		}

요렇게만 구현했습니다. 하지만 정점 1에서 정점 2까지의 간선이 2개 이상이면서 처음 간선이 (1,2,1) 두번째 간선이 (1,2,2)면
(1,2,1)의 최소 가중치 1을 (1,2,2)의 가중치 2로 덮어씌워져버려서 문제가 계속해서 틀렸습니다. 한 7,8시간 정도 삽질한 뒤에 문제를
제대로 파악하고 그 뒤에 위 코드를 

			for(Edge edge : vertax.edges) {
				if(vertax.w + edge.w < vList.get(edge.to).w) {
					vList.get(edge.to).w = vertax.w + edge.w;
					
					if(!vList.get(edge.to).isVisited) {
						pq.add(vList.get(edge.to));
					}else {
						vList.get(edge.to).isVisited = false;
						pq.add(vList.get(edge.to));
					}
					
				}
			}

수정하였습니다. 해당 코드는 시작점(혹은 시작점을 거친 방문하지 않으면서 가장 작은 가중치를 가진 중간 정점)에서부터 목적지까지의 모든 간선을 검사하여 기존의 거리보다 작은 경우 해당 거리를 갱신하고 간선 내 목적지 정점이 이전에 방문했을 경우 시작 정점(이 경우 완전 처음 출발 정점이 아니고 중간 정점입니다!!!!)이 달라졌기 때문에 목적지 간선의 방문여부를 다시 false로 초기화하여
<기존의 출발점에서 결과값이 더 작은 출발점 -> (중간정점) -> 목적지 정점 -> 그 이후 계산>방식으로 계산하도록 수정하였습니다.

저만 알아듣게 주저리주저리 쓴 듯 하네요 좀 더 알기 쉽게 정리해서 수정하겠습니다

처음에는 스스로 아이디어도 생각해내고 오래걸렸지만 스스로 구현도 해내서 뿌듯했는데 결국 문제를 잘못읽어서 뺑뺑 돌아온건 여전합니다.. 그리고 앞으로는 그래프 계산할때 어지간하면 배열 위주보다는 이런식으로 객체화하여 필요한 부분만 이용해서 메모리도 줄이는 방식으로 연습해야겠습니다.