C++로 그래프의 모든 노드를 방문하는 최단 경로 찾기

무방향 연결 그래프가 하나 주어지고, N개의 노드는 0, 1, 2, ..., N-1로 레이블되어 있다고 가정해 보겠습니다. graph 배열의 길이는 N이며, graph[i] 리스트에는 노드 i와 연결된 노드 j(i ≠ j)가 정확히 한 번씩 포함됩니다. 우리가 구해야 하는 것은 모든 노드를 방문하는 최단 경로의 길이입니다.

여기에는 몇 가지 유연한 조건이 있습니다. 시작 노드와 종료 노드는 자유롭게 선택할 수 있고, 이미 방문한 노드를 여러 번 다시 지나갈 수 있으며, 간선도 재사용이 가능합니다.

예를 들어 입력이 [[1],[0,2,4],[1,3,4],[2],[1,2]]라고 한다면 출력은 4가 됩니다. 이때 가능한 경로 중 하나는 [0,1,4,2,3]입니다.

해결 접근 방법

이 문제는 BFS(너비 우선 탐색)와 비트마스크(bitmask)를 결합하여 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 상태를 "현재 위치한 노드 + 지금까지 방문한 노드 집합"으로 표현하고, 이를 레벨(이동 횟수)별로 확장하는 것입니다. 그러면 가장 먼저 모든 노드를 방문하게 되는 시점의 레벨이 곧 최단 경로의 길이가 됩니다.

구체적인 단계는 다음과 같습니다.

• 큐(queue)를 하나 정의합니다.

• n := 그래프의 노드 개수

• req := (2^n) − 1 (모든 노드를 방문했음을 나타내는 목표 비트마스크)

• 방문 상태를 기록하기 위한 맵(visited)을 정의합니다.

• i := 0부터 i < n까지 반복하며 {0 OR (2^i), i}를 큐에 삽입합니다. (각 노드를 시작점으로 하는 초기 상태 생성)

• n이 1이라면 0을 반환합니다.

• lvl := 1부터 큐가 빌 때까지 lvl을 1씩 증가시키며 다음을 수행합니다.

  • sz := 현재 큐의 크기

  • sz가 0이 될 때까지 반복하며:

    • curr := 큐의 맨 앞 요소를 꺼냅니다.

    • i := 0부터 graph[curr[1]]의 크기까지 반복하며:

      • u := graph[curr[1]][i]

      • newMask := curr[0] OR (2^u)

      • 만약 newMask == req라면 lvl을 반환합니다. (모든 노드 방문 완료)

      • visited[u]에 newMask가 이미 존재하면 다음 반복으로 건너뜁니다.

      • visited[u]에 newMask를 삽입하고, {newMask, u}를 큐에 추가합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    int shortestPathLength(vector<vector<int> >& graph){
       queue<vector<int> > q;
       int n = graph.size();
       int req = (1 << n) - 1;
       map<int, set<int> > visited;
       for (int i = 0; i < n; i++) {
          q.push({ 0 | (1 << i), i });
       }
       if (n == 1)
       return 0;
       for (int lvl = 1; !q.empty(); lvl++) {
          int sz = q.size();
          while (sz--) {
             vector<int> curr = q.front();
             q.pop();
             for (int i = 0; i < graph[curr[1]].size(); i++) {
                int u = graph[curr[1]][i];
                int newMask = (curr[0] | (1 << u));
                if (newMask == req)
                   return lvl;
                if (visited[u].count(newMask))
                continue;
                visited[u].insert(newMask);
                q.push({ newMask, u });
             }
          }
       }
       return -1;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{1},{0,2,4},{1,3,4},{2},{1,2}};
    cout << (ob.shortestPathLength(v));
}

입력

{{1},{0,2,4},{1,3,4},{2},{1,2}}

출력

4

동작 원리 요약

비트마스크의 i번째 비트는 노드 i의 방문 여부를 나타냅니다. BFS는 레벨별로 상태를 확장하므로, 어떤 상태에서 처음으로 목표 비트마스크(req)에 도달하는 순간의 레벨이 곧 최단 경로의 길이가 됩니다. 또한 동일한 (노드, 마스크) 조합을 중복 처리하지 않도록 visited 맵으로 가지치기를 수행하기 때문에 탐색 효율이 보장됩니다. 전체 시간 복잡도는 상태 수가 최대 N × 2^N이므로 대략 O(N² × 2^N) 수준이며, 공간 복잡도 역시 O(N × 2^N)입니다.