[Java] leetcode 2492. Minimum Score of a Path Between Two Cities

문제

https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities/description/

Minimum Score of a Path Between Two Cities - LeetCode

정점 1 에서 n 까지 연결된 간선의 최소값을 찾는 문제

풀이

간선 탐색은 BFS 탐색으로 구현하였다.

풀이는 다음과 같다.

1. 이중 리스트로 그래프를 구현한다. 
2. BFS 탐색으로 모든 간선을 탐색한다.

 예제 그림에서 볼 수 있듯이 사이클의 경우 이미 탐색한 정점이라도 간선은 체크해야한다. 이 점만 주의하면 된다. 

코드

class Solution {
    ArrayList<ArrayList<int[]>> g;
    public int minScore(int n, int[][] roads) {
        g = new ArrayList<>();
        for(int i = 0 ;i < n+1;i ++){
            g.add(new ArrayList<>());
        }
        for(int x[] : roads){
            g.get(x[0]).add(new int[]{x[1], x[2]});
            g.get(x[1]).add(new int[]{x[0], x[2]});
        }
        Queue<Integer> Q = new LinkedList<>();
        boolean v[] = new boolean[n+1];
        int ans = Integer.MAX_VALUE;
        Q.offer(1);
        v[1] = true;
        while(!Q.isEmpty()){
            int nv = Q.poll();
            for(int x[] : g.get(nv)){
                ans = Math.min(ans, x[1]);
                if(!v[x[0]]){
                    v[x[0]] = true;
                    Q.offer(x[0]);
                }
            }
        }       
        return ans;
    }
}