Step-by-Step
[Java] Daily LeetCode Challenge 2492. Minimum Score of a Path Between Two Cities 본문
언어/JAVA
[Java] Daily LeetCode Challenge 2492. Minimum Score of a Path Between Two Cities
희주(KHJ) 2023. 3. 22. 13:01https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities/
흔히 보이는 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;
}
}
'언어 > JAVA' 카테고리의 다른 글
[Java] 백준 21611 - 마법사 상어와 블리자드 (0) | 2023.03.22 |
---|---|
[Java] 백준 23289 - 온풍기 안녕! (0) | 2023.03.22 |
[Java] Daily LeetCode Challenge 106. Construct Binary Tree from Inorder and Postorder Traversal (0) | 2023.03.16 |
[Java] Daily LeetCode Challenge 958. Check Completeness of a Binary Tree (0) | 2023.03.15 |
[Java] Daily LeetCode Challenge 23. Merge k Sorted Lists (0) | 2023.03.12 |
Comments