C++로 그래프의 최댓값 순열 구하는 방법

문제 개요

이 문제에서는 N개의 노드로 구성된 그래프가 주어지며, 우리의 목표는 수정된 배열의 최솟값이 가질 수 있는 최댓값을 찾는 것입니다.

여기서 그래프의 순열(permutation)이란, 각 위치에 대해 자신보다 왼쪽에 있으면서 공통 간선으로 서로 연결된 노드가 최소 1개 이상 존재하는 인덱스의 개수를 의미합니다.

예제로 문제 이해하기

입력 : N = 4, edge = {{1, 2}, {2, 3}, {3, 4}, {4, 1}}
출력 : 3

해결 접근 방법

이 문제를 해결하는 가장 간단한 방법은 한 노드에서 출발하여 인접한 모든 노드를 차례로 방문하며 그래프를 탐색하는 것입니다. 각 노드에 연결된 노드의 개수를 활용한 공식을 통해 순열의 최댓값을 계산할 수 있습니다.

핵심 공식은 다음과 같습니다.

순열 값 = (연결 요소의 크기) − 1

즉, 그래프를 여러 개의 연결 요소(component)로 나눈 뒤, 각 연결 요소의 크기에서 1을 빼고 모두 더하면 원하는 최댓값을 얻을 수 있습니다. 이는 깊이 우선 탐색(DFS)을 사용하면 효율적으로 구현할 수 있습니다.

구현 예제

아래 C++ 프로그램은 위에서 설명한 해결 방법의 동작 과정을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;

int dfs(int x, vector<int> adjMat[], int visited[]){
    int sz = 1;
    visited[x] = 1;
    for (auto ch : adjMat[x])
        if (!visited[ch])
            sz += dfs(ch, adjMat, visited);
    return sz;
}
int maxValPermutationGraph(int n, vector<int> adjMat[]){
    int val = 0;
    int visited[n + 1] = { 0 };
    for (int i = 1; i <= n; i++)
        if (!visited[i])
            val += dfs(i, adjMat, visited) - 1;
    return val;
}
int main(){
    int n = 4;
    vector<int> adjMat[n + 1] = {{1, 2}, {2, 3}, {3, 4}, {4, 1}};
    cout<<"그래프의 최댓값 순열은 "<<maxValPermutationGraph(n, adjMat);
    return 0;
}

실행 결과

그래프의 최댓값 순열은 3

위 예제에서 그래프는 4개의 노드가 하나의 사이클(연결 요소)을 이루고 있으므로, 공식에 따라 4 − 1 = 3이라는 결과가 도출됩니다.