[BOJ] BOJ_1753 최단경로 (JAVA)

[백준 1753번 최단경로]

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

[접근 방법]

'그래프의 한 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘' 인 

 다익스트라 알고리즘 반복 학습을 위해 이 문제를 선택하였다.

다익스트라 알고리즘을 이용하여 문제를 해결하고자 한다.

 

문제를 해결하는 동안 고려할 사항은 다음과 같았다.

1. 다익스트라 알고리즘을 사용한다.

2. 2차원 배열을 이용한다면 '메모리 초과' 문제가 발생한다.

3. 이를 해결하기 위해, 우선순위 큐를 사용한다.

 

[JAVA 코드 - 2차원 배열 -> "메모리 초과"]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_1753 {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int V = Integer.parseInt(st.nextToken()); // node
    int E = Integer.parseInt(st.nextToken()); // line

    int start = Integer.parseInt(br.readLine()); // 시작점

    int[][] arr = new int[V + 1][V + 1];
    for (int[] a : arr) {
      Arrays.fill(a, Integer.MAX_VALUE);
    }

    for (int i = 0; i < E; i++) {
      st = new StringTokenizer(br.readLine());
      int node1 = Integer.parseInt(st.nextToken());
      int node2 = Integer.parseInt(st.nextToken());
      int weight = Integer.parseInt(st.nextToken());
      arr[node1][node2] = Math.min(arr[node1][node2], weight); // 노드사이 가중치 최소값 갱신
    }

    int[] result = dijkstra(V, arr, 1);

    for (int i = 1; i < result.length; i++) {
      if (result[i] == Integer.MAX_VALUE) {
        bw.write("INF" + "\n");  
      } else {
        bw.write(result[i] + "\n");
      }
    }

    bw.flush();
    bw.close();
  }


  /**
   * n : 노드 개수
   * arr : 가중치 2차원 배열
   * start : 시작점
   */
  private static int[] dijkstra(int n, int[][] arr, int start) {

    int[] result = new int[n + 1];
    boolean[] visited = new boolean[n + 1];

    Arrays.fill(result, Integer.MAX_VALUE);
    result[start] = 0;
    visited[start] = true;

    for (int i = 1; i <= n; i++) {
      if (!visited[i] && arr[start][i] != Integer.MAX_VALUE) {
        result[i] = arr[start][i];
      }
    }

    // 최소 거리 노드 찾기
    for (int i = 1; i < n; i++) {

      int min = Integer.MAX_VALUE;
      int min_index = -1;

      // 탐색 안한 노드 중에 현재 최소 거리 노드 => 앞으로 탐색할 노드
      for (int j = 1; j <= n; j++) {
        if (!visited[j]) {
          if (result[j] < min) {
            min = result[j];
            min_index = j;
          }
        }
      }

      if (min_index == -1) {
        break;
      }

      // 거쳐가는것과 비교해 최솟값 갱신
      visited[min_index] = true;
      for (int j = 1; j <= n; j++) {
        if (!visited[j] && arr[min_index][j] != Integer.MAX_VALUE) {
          if (result[min_index] + arr[min_index][j] < result[j]) {
            result[j] = result[min_index] + arr[min_index][j];
          }
        }
      }

    }

    return result;
  }

}

위와 같이 2차원 배열을 이용한 방법은 '메모리 초과' 로 인해 실패 했다.

 

[JAVA 코드 - 우선순위 큐 -> "맞았습니다!!"]

정점을 별도의 클래스로 만들어서 구현한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;



class Node implements Comparable<Node> {
  int index;
  int cost;

  public Node(int index, int cost) {
    this.index = index;
    this.cost = cost;
  }

  @Override
  public int compareTo(Node o) {
    return Integer.compare(this.cost, o.cost);
  }
}


public class BOJ_1753 {

  static ArrayList<Node>[] graph;

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int V = Integer.parseInt(st.nextToken()); // 정점의 개수 V
    int E = Integer.parseInt(st.nextToken()); // 간선의 개수 E

    int K = Integer.parseInt(br.readLine()); // 시작 정점

    graph = new ArrayList[V+1];
    for (int i = 0; i <= V; i++) graph[i] = new ArrayList<>();
    //(u, v, w)
    for (int i = 1; i <= E; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken());
      int v = Integer.parseInt(st.nextToken());
      int w = Integer.parseInt(st.nextToken());

      graph[u].add(new Node(v, w));
    }

    int[] result = dijkstra(V, graph, K);
    for (int i = 1; i <= V; i++) {
      if (result[i] == Integer.MAX_VALUE) {
        bw.write("INF" + "\n");
      } else {
        bw.write(result[i] + "\n");
      }
    }

    bw.flush();
    bw.close();
  }

  /**
   * n : 노드 개수
   * arr : 가중치 2차원 배열
   * start : 시작점
   */
  private static int[] dijkstra(int n, ArrayList<Node>[] graph, int start) {

    int[] result = new int[n + 1];
    boolean[] visited = new boolean[n + 1];

    Arrays.fill(result, Integer.MAX_VALUE);
    result[start] = 0;
    visited[start] = true;

    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.offer(new Node(start, 0));

    while (!pq.isEmpty()) {
      int currentNode = pq.poll().index;

      visited[currentNode] = true;

      for (Node next : graph[currentNode]) {
        if (result[next.index] > result[currentNode] + next.cost) {
          result[next.index] = result[currentNode] + next.cost;

          pq.offer(new Node(next.index, result[next.index]));
        }
      }
    }

    return result;
  }

}

 

[Rewind]

1. 어려웠던 점

- 2차원 배열로 정점 사이 간선의 가중치를 표현하는 방식이 메모리 초과를 유발하여, 그래프 방식과 우선순위 큐 방식으로 구현하는 것이 익숙치 않았다.

- 다익스트라 알고리즘에 아직 익숙하지 않아 머리속으로 구현 과정이 곧바로 떠오르지 않았다.

 

2. 알게된 점

- 우선순위 큐를 이용하는 방법을 알게 되었다.

- 그래프 구조를 구현하는 방법을 알게 되었다.

- 다익스트라 알고리즘에 대해 조금더 익숙하게 되었다.

 

3. 개선할 점

- 다익스트라 알고리즘에 대한 확실한 이해가 필요하다.

- 우선순위 큐, 그래프 구조 등 자바 환경에서 다양한 자료구조를 다룰 줄 알아야 한다.