문제 접근
모든 간선(E)의 가중치가 다른 그래프에서 시작점으로부터 이동할 수 있는 모든 정점(V)들에 대한 최단 경로를 구하는 문제
연결된 간선간의 이동거리가 동일하지 않기 때문에 bfs를 통해 모든방향을 탐색하며 이동하기에는 비효율 적인 부분이 있다.
목표 정점까지 이동하기 위해서는 이어진 간선들중 짧은 거리를 가진 간선을 선택해서 이동할 필요가 있다. (탐욕적 접근)
그러기 위해서는 데이크스트라 알고리즘이 필요하다.
깊이 우선 탐색(dfs)에서 최적해를 찾기 위해 유망하지 않은 가능성은 사전에 차단하는 가지치기 방식의 백트래킹이 있다면
너비 우선 탐색(bfs)에서 비용이 가장 적은 경로를 찾기 위해 매 순간 가장 최선의 경우의 수를 선택하는 것이 데이크스트라이다.
문제 조건 확인
- 정점(V)의 개수는 1 <= V <= 20,000 이다.
- 정점간 연결되는 간선(E)의 개수는 1 <= E <= 300,000 이다.
- 간선 정보는 세 개의 정수 u, v, w 가 순서대로 주어지며 u -> v 정점으로 가는 가중치 w의 간선 형태로 주어진다 (w는 10 이하의 자연수)
- 최단경로 출력
- 시작점 자신은 0으로 출력
- 경로가 존재하지 않으면 INF 출력
문제 설계
입력
입력
- 입력량이 많기 때문에
BufferdReader사용 (최대 간선 갯수 30만)
자료구조
- 정점의 최대 갯수가 2만개 이기 때문에 2차원 배열로 관리하려면 [20001][20001] 만큼의 메모리가 필요하다 -> 높은 확률로 메모리 초과가 발생
Map을 사용한 인접리스트를 사용key값은 출발 지점value값은 도착지점과 이동비용을int[]형태로 저장
- 중복 방문을 방지하기 위한
visited배열 생성 - 시작 정점으로부터 각 정점까지 최단 거리를 저장할 배열
result배열 생성 - 각 단계별 간선 정보들 중 최솟값을 우선적으로 탐색하기 위한
PriorityQueue사용
로직
최단거리 탐색 메서드 djikstra(int start)
- 시작 정점의 번호를 파라미터 값으로 받음
PriorityQueue생성 시 꺼내는 객체의 최솟값 기준을 설정
2-1. 이동간 거리가 짧은 것을 기준으로 해야 함
2-2.int[] {도착지, 거리}형태로 입력받고 있기 때문에 거리를 비교하도록comparator설정- 시작 정점 방문처리 후 해당 정점과 연결된 정점들의 정보를
queue에 입력 queue가 비어있을 때까지 반복문 수행
4-1.pq를 통해 최솟값을 뽑아와 현재 방문 정점과 이동 거리를 뽑아옴- 현재 정점이 방문하지 않은 상태면 방문처리 후 현재까지 이동거리를 저장
5-1. 방문된 상태면total값을 저장된 값과 비교한뒤 작은 경우 갱신 - 현재 정점과 연결된 다음 정점들의 정보를 불러온 후 현재 이동거리
total에 다음 정점과의 이동거리를 더한 후queue에 추가
출력
- 각 정점으로의 최단거리를 출력해야함 최대 2만개
- 2만개를 시스템콜을 하게 될 경우 시간 초과 발생 가능성이 높음 ->
Stringbuilder로 모든 최단거리 정보를 입력한 후 한번에 출력
- 2만개를 시스템콜을 하게 될 경우 시간 초과 발생 가능성이 높음 ->
0에 대한 처리 최단거리가0이 나올 수 있는 경우의 수는 시작 정점과 이동할 수 없는INF상황if문을 통해 구분하여StringBuilder에 입력
구현 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
/*
* 데이크스트라
* 단방향 그래프
* 시작 노드에서 각 정점으로 이동하는 최소거리 구하기
* 자기 자신은 0
* 이동 못하면 INF
*
* 이동하려는 정점과 정점까지의 거리를 같이 관리해야한다.
* 우선순위 큐에서 최솟값을 뽑아내기 위한 기준을 설정하는 것이 포인트
*/
public class gold4_1753_Djikstra {
// 2차원 배열을 만들어 관리하게 될 경우 30만x30만은 많은 공간을 잡아먹게 됨
static Map<Integer, List<int[]>> graph;
static PriorityQueue<int[]> queue;
static boolean[] visited;
static int[] result;
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 startVer = Integer.parseInt(br.readLine());
graph = new HashMap<>();
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
if (graph.get(start) == null) {
graph.put(start, new ArrayList<>());
}
graph.get(start).add(new int[] {end, d});
}
// 각 정점의 방문처리를 도울 배열 생성 (0번 인덱스 사용x)
visited = new boolean[V+1];
// 결과 출력용 (0번 인덱스 사용 x)
result = new int[V+1];
djikstra(startVer);
StringBuilder sb = new StringBuilder();
// StringBuilder 에 각 정점 방문 최소횟수 한번에 입력
for (int i = 1; i < result.length; i++) {
// 0인 경우 처리
if (result[i] == 0) {
// 시작 노드인 경우 0
if (i == startVer) {
sb.append(0).append("\n");
} else { // 그 외에는 갈 수 없는 지역
sb.append("INF").append("\n");
}
} else { // 0이 아니면 추가
sb.append(result[i]).append("\n");
}
}
System.out.println(sb.toString());
}
public static void djikstra(int startVer) {
// 거리 기준 최솟값을 먼저 뽑아내기
queue = new PriorityQueue<>((o1, o2) -> (o1[1] - o2[1]));
List<int[]> list = graph.get(startVer);
// 시작 노드 방문 처리
visited[startVer] = true;
for (int[] arr: list) {
// 현재 정점에서 다음 정점까지의 거리 입력
queue.add(arr);
}
while (!queue.isEmpty()) {
// 큐에서 간선의 거리가 짧은 list 꺼내기
int[] cur = queue.poll();
// 현재 방문 정점과 누적 거리
int nowVer = cur[0];
int total = cur[1];
// 현재 정점 방문 확인
if (!visited[nowVer]) { // 방문하지 않은 경우
// 방문 처리
visited[nowVer] = true;
result[nowVer] = total;
} else { // 방문한 경우
// 방문된경우 최솟값인지 확인
if (result[nowVer] > total) {
// 더 짧을 경우 갱신
result[nowVer] = total;
} else {
// 아니면 다음 진행
continue;
}
}
// 현재 방문 정점에서 방문 가능한 정점 리스트 가져오기
List<int[]> nextList = graph.get(nowVer);
// 순회 (nextList가 null이 아닌 경우)
// 방문할 정점이 없으면 다음으로
if (nextList == null) {
continue;
}
// 있으면 순회
for (int i = 0; i < nextList.size(); i++) {
// 다음 방문할 정점과 거리
int[] next = nextList.get(i);
int nextVer = next[0];
int nextD = next[1];
// 현재 누적 거리 합에 nextD를 더한 뒤 queue에 추가
queue.add(new int[] {nextVer, total + nextD});
}
}
}
}
주요 코드
연결 상태 관리
PriorityQueue의 최솟값 추출 기준 설정
코드 개선
그래프 이동경로 관리
- 구현 코드에서는
Map자료구조를 통해value값을int[]배열을 생성해서 받고 있음Node클래스를 구현하기 -> 좀 더 {정점, 가중치} 관계를 명확히 표현할 수 있음
출력 관리
0이 시작지점과 불가능 경로INF를 같이 표시하고 있어StringBuilder에 추가할 때0을 먼저 확인하고 그것이 시작지점인지 아닌지를 한번 더 확인하고 있음INF는Integer의 최댓값인Integer.MAX_VALUE로 관리하면if문을 중첩해서 사용할 필요가 없어진다.
방문처리
- 구현 코드에서는 시작지점을 방문처리 후 연관된 정점들을
queue에 넣은 상태로 반복문을 진행 - 데이크스트라의 핵심은
queue에서 꺼낸 정점v는 시작점에서v까지 최단거리가 확정된 것
->visited[nowVer]가true라는 것은 이미 최단 경로를 찾았다는 의미 ->else블록에서 비교값을 갱신하는 행위는 불필요한 작업
개선된 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
/*
* 데이크스트라
* 단방향 그래프
* 시작 노드에서 각 정점으로 이동하는 최소거리 구하기
* 자기 자신은 0
* 이동 못하면 INF
*
* 이동하려는 정점과 정점까지의 거리를 같이 관리해야한다.
* 우선순위 큐에서 최솟값을 뽑아내기 위한 기준을 설정하는 것이 포인트
*/
public class gold4_1753_refactoring {
// 2차원 배열을 만들어 관리하게 될 경우 30만x30만은 많은 공간을 잡아먹게 됨
static Map<Integer, List<Node>> graph;
static PriorityQueue<Node> queue;
// boolean 배열 없이 result 배열만으로 충분
static int[] result;
// Node 객체를 만들어 정점과 이동비용을 관리
static class Node implements Comparable<Node> {
int ver;
int cost;
public Node(int ver, int cost) {
this.ver = ver;
this.cost = cost;
}
// 최솟값 비교 기준을 cost로 설정
@Override
public int compareTo(Node o) {
return this.cost - o.cost;
}
}
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 startVer = Integer.parseInt(br.readLine());
graph = new HashMap<>();
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
if (graph.get(start) == null) {
graph.put(start, new ArrayList<>());
}
graph.get(start).add(new Node(end, d));
}
// 결과 출력용 (0번 인덱스 사용 x)
result = new int[V+1];
for (int i = 0; i < result.length; i++) {
result[i] = Integer.MAX_VALUE;
}
djikstra(startVer);
StringBuilder sb = new StringBuilder();
// StringBuilder 에 각 정점 방문 최소횟수 한번에 입력
for (int i = 1; i < result.length; i++) {
if (result[i] == Integer.MAX_VALUE) {
sb.append("INF").append("\n");
} else {
sb.append(result[i]).append("\n");
}
}
System.out.println(sb.toString());
}
public static void djikstra(int startVer) {
queue = new PriorityQueue<>();
// 시작 노드 처리 후 queue에 add
result[startVer] = 0;
queue.add(new Node(startVer, 0));
while(!queue.isEmpty()) {
Node cur = queue.poll();
int nowVer = cur.ver;
int cost = cur.cost;
// 이미 처리된 정보면 다음으로
if (result[nowVer] < cost) {
continue;
}
// 인접지역 없음 다음으로
if (graph.get(nowVer) == null) {
continue;
}
for (Node nodeNext : graph.get(nowVer)) {
int next = nodeNext.ver;
int nextCost = cost + nodeNext.cost;
// 더 짧은 경로를 발견한 경우
if (nextCost < result[next]) {
// 갱신 후
result[next] = nextCost;
// 큐에 추가
queue.add(new Node(next, nextCost));
}
}
}
}
}
회고
처음에는 단순히 bfs 구조에 pq만 사용하는 줄 알았는데 생각보다 정점 정보 관리와 정보가 두개 이상일때 최솟값을 꺼내는 기준을 정해야 하는 등 조건들이 많이 추가되기 때문에 고민을 많이 했고 구현한 코드를 리팩토링 하는 과정에서 내가 코드를 비효율적으로 작성하고 있다는 것을 알게 되었다. 지금은 많이 부족한 단계이기 때문에 비효율적 코드라도 문제해결을 위해서라면 작성하지만 실력이 좀 올라오게 되면 설계단계에서 좀더 효율적으로 코드를 작성할 수 있게 고민하는 시간을 가져보면 좋을 것 같다.
안녕하세요