[baekjoon] 20168 골목 대장 호석 - 기능성

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

https://www.notion.so/1f167f8e832781bfa0f3ce36f0c51641

오늘 문제는 오랜만에 다익스트라!!

 

풀 수 있는 방법은 백트래킹, 다익스트라 등 여러 방법이 존재한다.

 

다만 문제에 오류가 있는 듯 하다.

7 7 1 6 4
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
1 7 2
7 5 1

위의 테스트 케이스로 2가 나와야 정상이다.

다만 스터디원의 한분은 -1이 나왔지만 테스트를 통과하였다.

 

import java.io.*;
import java.util.*;

public class Main {
  public static ArrayList<ArrayList<int[]>> map = new ArrayList<>();
  public static int N, M, A, B, C;
  public static int[] visited;


  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    input(br);
    pro();
  }

  static void pro()  {
    PriorityQueue<int[]> pq = new PriorityQueue<>(
        (x, y) -> Integer.compare(x[1], y[1])
    );

    pq.add(new int[]{A,0,0});

    while(!pq.isEmpty()){
      int[] cur = pq.poll();
      int x = cur[0];
      int fee = cur[1];
      int total = cur[2];
      if(x == B){
        System.out.println(fee);
        return;
      }
      if(visited[x] < total) continue;
      visited[x] = total;

      for(int[] route : map.get(x)){
        int nx = route[0];
        int nf = Math.max(fee, route[1]);
        int nt = total + route[1];
        if(nt > C) continue;

//        System.out.println(x + "->" + nx +" :"+ nt + " " + nf);
        pq.add(new int[]{nx, nf, nt});
      }
    }
    System.out.println(-1);
  }

  static void input(BufferedReader br) throws Exception {
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    A = Integer.parseInt(st.nextToken());
    B = Integer.parseInt(st.nextToken());
    C = Integer.parseInt(st.nextToken());
    map = new ArrayList<>();
    visited = new int[N+1];
    for(int i = 0; i <= N; i++){
      map.add(new ArrayList<>());
      visited[i] = Integer.MAX_VALUE;
    }

    for(int i=0 ; i<M ; i++){
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      int c = Integer.parseInt(st.nextToken());
      map.get(a).add(new int[]{b,c});
      map.get(b).add(new int[]{a,c});
    }

  }

}

 

위의 코드는 나의 코드인데 스터디원과 다른 부분은 visited 부분이다.

나는 visited 체크를 int로 해서 거리가 visited보다 크면 continue해주었다.

 

그래서 나는 2로 정답이 나왔다.

흠.. 여기서 더 예외 케이스가 있을지 궁금하다!