[Java] Daily LeetCode Challenge 2492. Minimum Score of a Path Between Two Cities

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

Minimum Score of a Path Between Two Cities - LeetCode

 

흔히 보이는 BFS 문제

 

주의할 점은 시작이 1이고 끝이 n이기만 하면 된다는 점!

중간에 1을 방문하거나 n을 방문해도 상관없다.

 

연결된 노드와 가중치 값은 HashMap을 이용해서 저장했다. 숏코딩은 아님

 

[코드]

class Solution {
    public int minScore(int n, int[][] roads) {
        int start = 1, end = n;

        HashMap<Integer, ArrayList<int[]>> hm = new HashMap<>();
        for(int i=0; i<roads.length; i++){
            int a = roads[i][0], b = roads[i][1], w = roads[i][2];

            ArrayList<int[]> arr = hm.getOrDefault(a, new ArrayList<>());
            arr.add(new int[] {b,w});
            hm.put(a, arr);

            arr = hm.getOrDefault(b, new ArrayList<>());
            arr.add(new int[] {a,w});
            hm.put(b, arr);
        }

        boolean[] visited = new boolean[n+1];
        visited[start]=true;

        Queue<Integer> q = new LinkedList<>();
        q.add(start);

        int len = Integer.MAX_VALUE;
        while(!q.isEmpty()){
            int node = q.poll();

            if(node == 1)
                System.out.println(hm.get(node).size());

            for(int[] p : hm.getOrDefault(node, new ArrayList<>())){
                len = Math.min(p[1], len);
                if(visited[p[0]])
                    continue;
                visited[p[0]]=true;
                q.add(p[0]);
            }
        }
        return len;
    }
}