https://school.programmers.co.kr/learn/courses/30/lessons/132266
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
이 문제는 특정 목적지에서 여러 출발지까지의 최소 이동 거리를 구하는 문제다.
주어진 그래프는 양방향 도로로 연결되어 있으며,
BFS를 사용해 목적지로부터 각 노드까지의 거리를 계산한다.
먼저 solution 메서드는 입력으로 주어진 그래프 정보를 graph 리스트 배열로 초기화하고,
각 노드의 거리를 저장할 cost 배열을 -1로 초기화하여 방문 여부와 거리를 동시에 관리한다.
그런 다음, 모든 도로 정보를 읽어 graph에 양방향으로 저장한다.
핵심은 bfs 메서드로, 목적지에서 출발해 각 노드로의 최단 거리를 구한다.
큐를 사용해 BFS를 구현하며, 큐에서 노드를 하나씩 꺼내 해당 노드와 연결된 노드를 탐색한다.
아직 방문하지 않은 노드(cost[num] == -1)는 큐에 추가하고,
현재 노드까지의 거리에서 1을 더한 값을 해당 노드의 거리로 설정한다. 이렇게 하면 최단 거리가 자동으로 계산된다.
최종적으로 각 출발지 노드가 저장된 sources 배열을 순회하며, cost 배열에서 각 노드의 거리를 가져와 결과 배열에 저장한다.
만약 어떤 출발지가 목적지에 도달할 수 없는 경우, 그 값은 초기값인 -1로 유지된다.
마지막으로 결과 배열을 반환해 각 출발지에서 목적지까지의 최소 거리를 반환한다.
import java.util.*;
class Solution {
List<Integer>[] graph;
int[] cost;
public int[] solution(int n, int[][] roads, int[] sources, int destination) {
graph = new ArrayList[n+1];
for(int i = 0 ; i <= n ; i++) graph[i] = new ArrayList<>();
for(int[] road : roads){
graph[road[0]].add(road[1]);
graph[road[1]].add(road[0]);
}
cost = new int[n+1];
Arrays.fill(cost,-1);
bfs(destination);
return Arrays.stream(sources)
.map(idx->cost[idx])
.toArray();
}
private void bfs(int start){
Queue<Integer> q = new ArrayDeque<>();
q.add(start);
cost[start] = 0;
while(!q.isEmpty()){
int now = q.poll();
int len = graph[now].size();
for(int i = 0 ; i < len ; i++){
int num = graph[now].get(i);
if(cost[num] == -1){
q.add(num);
cost[num] = cost[now] + 1;
}
}
}
}
}
'Algorithm & Data Structures > Programers' 카테고리의 다른 글
Lv 3. [1차] 셔틀버스 (0) | 2024.11.26 |
---|---|
Lv 3. 가장 긴 펠린드롬 (3) | 2024.11.21 |
Lv 3. 경주로 건설 (1) | 2024.11.13 |
Lv 3. 디스크 컨트롤러 (1) | 2024.11.11 |
Lv 3. 연속 펄스 부분 수열의 합 (0) | 2024.11.07 |