[DAY94] Algorithm : Return to Base

강철부대원들이 각자의 위치에서 부대로 복귀하는 최단 시간을 구하는 문제다. 부대원은 여러 명이지만 목적지는 하나다. 각 부대원마다 BFS를 돌리면 시간 초과가 발생하므로, 목적지에서 출발하여 모든 지역으로 퍼져나가는 BFS를 단 한 번만 수행하는 '역발상'이 핵심이다.

---

❓ 문제 분석

• 목표: 여러 시작점(sources)에서 하나의 도착점(destination)까지 가는 각각의 최단 시간 구하기.
• 제약 조건:
  • 지역(노드) 수 $N$: 최대 100,000 / 도로(간선) 수 $E$: 최대 500,000
  • 부대원 수: 최대 500명
  • 각 부대원마다 BFS를 돌리면 $500 \times O(N+E)$가 되어 비효율적이다.
  • 간선의 가중치가 모두 1이므로 BFS(너비 우선 탐색)가 최단 거리 알고리즘으로 적합하다.
• 핵심 키워드: "최단 시간", "왕복 가능(양방향)", "복귀 불가능 시 -1"

---

💡 풀이 설계

1. 시도했던 접근 (Many-to-One)

• 처음엔 문제 그대로 각 부대원(source) 위치에서 출발하여 destination을 찾는 BFS를 생각했다.
• 하지만 부대원이 많을수록 연산 횟수가 정직하게 늘어나는 구조라 효율성이 떨어진다고 판단했다.

2. 최종 해결책 (One-to-Many, Reverse BFS) 💡

• 발상의 전환: 길이 양방향(왕복)이므로, "각자 부대로 오는 길"이나 "부대에서 각자에게 가는 길"이나 거리는 똑같다.
• 전략: destination을 시작점으로 잡고 BFS를 단 한 번만 수행한다. 이렇게 하면 한 번의 탐색으로 모든 지역까지의 최단 거리를 알 수 있다.
• 자료구조:
  • vector<vector<int>> graph: 인접 리스트로 지도 구현.
  • vector<int> dist: 거리 배열. 초기값을 -1로 설정하여, 방문하지 않음(Unvisited)과 도달 불가(Unreachable) 상태를 동시에 표현한다.
• 알고리즘 흐름:
  1. 양방향 그래프를 생성한다.
  2. dist 배열을 -1로 초기화하고, destination의 거리는 0으로 설정해 큐에 넣는다.
  3. BFS를 돌며 연결된 지역의 거리를 현재 거리 + 1로 갱신한다.
  4. BFS가 끝난 후, sources 배열 순서대로 dist 값을 읽어서 정답을 채운다.

---

💻 코드 구현

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    // 지도 만들기: 인접 리스트 생성
    // 노드 번호가 1~n이므로 크기는 n + 1
    vector<vector<int>> graph(n + 1);
    for (const auto& road : roads) {
        int u = road[0];
        int v = road[1];
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    // 준비: 거리 배열과 큐
    // 모든 거리를 -1로 초기화하여 '방문 안 함'과 '도달 불가'를 동시에 처리
    vector<int> dist(n + 1, -1);
    queue<int> q;

    // 역발상: 도착지(강철부대)에서 출발
    dist[destination] = 0;
    q.push(destination);

    // 탐색 시작 (BFS)
    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (int next : graph[curr]) {
            // 아직 방문하지 않은 노드라면 거리 갱신
            if (dist[next] == -1) {
                dist[next] = dist[curr] + 1;
                q.push(next);
            }
        }
    }

    // 정답 추출: 요청받은 부대원 순서대로 거리값 저장
    vector<int> answer;
    for (int s : sources) {
        answer.push_back(dist[s]);
    }

    return answer;
}

---

🐛 시행착오 및 디버깅

• 초기화 값: 처음엔 도달 불가능한 경우를 나중에 따로 처리하려 했으나, 애초에 거리 배열을 -1로 초기화해두면 BFS가 닿지 않은 곳은 자연스럽게 -1로 남게 되어 코드가 훨씬 간결해졌다.
• 인덱스 주의: 문제에서 지역 번호가 1부터 시작하므로, 배열 크기를 n이 아닌 n+1로 잡아야 Out of Bound 에러를 피할 수 있다.

---

✅ 오늘의 회고

항목	내용
유형	그래프 탐색 (Graph), BFS
체감 난이도	중 (역발상 아이디어가 중요함)
복잡도	시간: $O(N + E)$, 공간: $O(N + E)$
새로 배운 것	"다수 $\to$ 하나"의 최단 거리는 "하나 $\to$ 다수"로 방향을 뒤집어 생각하면 연산량을 획기적으로 줄일 수 있다는 점을 배웠다.