본문으로 건너뛰기

1. 문제 분석​

1.1 문제의 핵심 요구사항​

  • 여러 출발지(sources)에서 하나의 도착지(destination)까지의 최단 거리를 구해야 함
  • 모든 경로의 비용이 1로 동일함
  • 도달할 수 없는 경우 -1을 반환해야 함

1.2 접근 방법 검토​

  • 최단 경로 문제에서 일반적으로 고려할 수 있는 알고리즘들:
    • 다익스트라 알고리즘: O(E log V)
    • 플로이드-워셜 알고리즘: O(V³)
    • BFS(너비 우선 탐색): O(V + E)
팁

모든 간선의 가중치가 1로 동일할 때는 BFS로 최단 경로를 구할 수 있습니다. 이는 BFS가 방문하는 순서대로 최단 거리가 보장되기 때문입니다.

팁

이 문제의 핵심은 역방향 접근입니다. 각 출발지에서 목적지까지의 거리를 구하는 대신 목적지에서 모든 노드까지의 거리를 한 번만 구하면 됩니다.

1.3 시간 복잡도 분석​

  • 문제의 제한사항:
    • 정점(V) 수: 최대 100,000
    • 간선(E) 수: 최대 500,000
    • 출발지 수: 최대 500
  • 각 알고리즘의 시간 복잡도를 계산해보면:
    • 다익스트라: O(E log V) ≈ O(500,000 log 100,000)
    • 플로이드-워셜: O(V³) ≈ O(100,000³)
    • BFS: O(V + E) ≈ O(100,000 + 500,000) = O(600,000)
정보

BFS가 가장 효율적인 선택입니다. 또한 구현이 간단하고 직관적이라는 장점도 있습니다.

2. 문제 풀이​

2.1 풀이 전략​

  1. 목적지에서 시작하여 모든 정점까지의 거리를 한 번에 계산
  2. 각 출발지의 거리를 조회하여 결과 배열 생성

2.2 구현 코드​

public int[] solution(int n, int[][] roads, int[] sources, int destination) {
    // 1. 그래프 구성
    Map<Integer, List<Integer>> graph = new HashMap<>();
    for(int[] road: roads) {    
        graph
            .computeIfAbsent(road[0], key -> new ArrayList<>())
            .add(road[1]);
        graph
            .computeIfAbsent(road[1], key -> new ArrayList<>())
            .add(road[0]);
    }
    
    // 2. BFS로 최단 거리 계산
    int[] visited = new int[n + 1];
    Arrays.fill(visited, -1);
    visited[destination] = 0;
    
    Queue<Integer> queue = new LinkedList<>();
    queue.add(destination);
    
    while(!queue.isEmpty()) {
        int node = queue.remove();
        
        for(int nextNode: graph.get(node)) {
            if(visited[nextNode] != -1) 
                continue;
            
            visited[nextNode] = visited[node] + 1;
            queue.add(nextNode);
        }
    }
    
    // 3. 결과 배열 생성
    return Arrays
        .stream(sources)
        .map(s -> visited[s])
        .toArray();
}

2.3 코드 설명​

  1. 그래프 구성
    • 양방향 그래프이므로 양쪽 모두에 간선 정보 추가
    • computeIfAbsent를 사용하여 간결하게 구현
  2. BFS 구현
    • 목적지에서 시작하여 모든 정점까지의 거리 계산
    • 방문 배열을 -1로 초기화하여 도달 불가능한 정점 표시
    • 큐를 사용하여 BFS 구현
  3. 결과 생성
    • 스트림을 활용하여 각 출발지의 거리값을 매핑
    • 방문하지 못한 정점은 초기값 -1이 그대로 유지됨

4. 마치며​

  • 이 문제는 최단 경로 문제이지만, 모든 간선의 가중치가 1이라는 특성을 활용하여 BFS로 간단하게 해결할 수 있었습니다.
  • 문제의 제약 조건을 잘 분석하여 적절한 알고리즘을 선택하는 것이 중요함을 보여주는 좋은 예시입니다.