[BOJ] 1753 최단경로 - JAVA

1. 문제

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

1753번: 최단경로

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

---

2. 풀이

Node 클래스

• implements Comparable한다. 우선순위 큐에서 사용할 수 있도록 하기 위함이다. 
• 가중치 순으로 비교한다.

static class Node implements Comparable<Node>{
   int v,w;
   private Node(int v, int w){
      this.v = v;
      this.w = w;
   }

   @Override
   public int compareTo(Node o) {
      return this.w-o.w;
   }
}

 

입력

• 리스트를 쓸거라면 꼭!!! LinkedList가 아니라 ArrayList를 써야한다. 이 걸 강조하는 이유는 내가 이 한줄때문에 몇 시간을 허비했기 때문이다.

static List<Node>[] adj;

//...중략

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());

int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(in.readLine()) - 1;

adj = new ArrayList[V];
for (int i = 0; i < V; i++) adj[i] = new ArrayList<>();

for (int e = 0; e < E; e++) {
      st = new StringTokenizer(in.readLine());
      int u = Integer.parseInt(st.nextToken()) - 1;
      int v = Integer.parseInt(st.nextToken()) - 1;
      int w = Integer.parseInt(st.nextToken());

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

 

탐색 - Dijkstra (feat. PriorityQueue)

• 최소 거리 배열, 방문여부 배열을 만든다. 
• 최소 거리 배열은 가능하지 않은 가장 큰 값을 넣는다.
• 시작 거리에 0을 저장한다.
• 우선순위 큐를 이용한다. Node의 compareTo를 사용해서 가중치가 작은 순서대로 정렬된다.
• 가장 가중치가 작은 것을 큐에서 뽑는다.
• 그 위치를 이미 방문했다면(=이미 최솟값이 완성되었다면) 반복문의 처음으로 돌아간다.
• 방문한 적 없다면 지금 값이 바로 해당 위치의 최솟값이므로 방문여부를 저장한다.
• 해당 위치의 연결리스트를 하나씩 돌면서 다음 위치를 탐색한다.
  • 다음위치를 방문한 적 있거나 그 위치에 저장된 거리값이 지금 저장하려는 값보다 작으면 넘어간다. 
  • 위의 경우에 해당되지 않는다면 거리값을 수정하고 큐에 새로운 값을 가중치와 인덱스 함께 넣는다.

int[] distance = new int[V];
boolean[] visited = new boolean[V];
Arrays.fill(distance,Integer.MAX_VALUE);
distance[K] = 0;

PriorityQueue<Node> pQueue = new PriorityQueue<>();
pQueue.offer(new Node(K,distance[K]));

while (!pQueue.isEmpty()) {
      Node current = pQueue.poll();
      if(visited[current.v]) continue;
      visited[current.v] = true;

      for(int i=0,size = adj[current.v].size();i<size;i++){
            int v = adj[current.v].get(i).v;
            int w = adj[current.v].get(i).w;
            if(!visited[v] && distance[v]>current.w+w){
                  distance[v] = current.w+w;
                  pQueue.offer(new Node(v,distance[v]));
            }
      }
}

 

출력

• 방문한 적 있는 곳만 출력하고 방문한 적 없다면 INF를 출력한다.

StringBuilder sb = new StringBuilder();
for (int i=0;i<V;i++) {
   if (visited[i]) sb.append(distance[i]);
   else sb.append("INF");
   sb.append("\n");
}
System.out.print(sb);

---

3. 결과

뭐가 문제인지 정말 많이 고민했는데 LinkedList때문이었다.