n개의 정점으로 이루어진 그래프가 주어져 있다고 가정해 보겠습니다. 정점은 1부터 n까지 번호가 매겨져 있으며, 배열 edges에 담긴 간선들로 서로 연결되어 있습니다. 또한 각 정점은 배열 values에 저장된 1부터 n 사이의 값을 하나씩 가지며, 이를 해당 정점의 'x' 값이라고 합니다.
이제 그래프에서 슈퍼 꼭짓점(super vertex)을 찾아야 합니다. 정점 i는 다음 조건을 만족할 때 슈퍼 꼭짓점이라고 부릅니다.
정점 1에서 정점 i까지의 최단 경로 위에, i번째 정점과 동일한 'x' 값을 가진 다른 정점이 존재하지 않아야 한다.
즉, 루트(정점 1)에서 해당 정점까지 이어지는 경로 상에서 자신과 같은 값을 가진 정점이 처음 등장하는 경우에만 슈퍼 꼭짓점이 됩니다. 이 조건을 만족하는 모든 정점을 출력하면 됩니다.
예시
입력이 다음과 같다고 해보겠습니다.
- n = 5
- values = {1, 2, 2, 1, 3}
- edges = {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}}
그렇다면 출력 결과는 1, 3, 4, 5입니다.
정점 2를 제외한 모든 정점이 조건을 만족하기 때문에, 정점 2만 제외됩니다. 정점 1에서 정점 2로 가는 경로에는 정점 1(x = 1)이 있고, 정점 2의 x 값도 2가 아닌... 즉 정점 2(x = 2)는 경로상 자신과 같은 값을 가진 선행 정점이 있는 것이 아니라, 정점 3(x = 2)이 정점 2 뒤에 오지만 정점 2 자체는 경로 시작점인 정점 1(x = 1)과 값이 달라야 하는데, 실제로는 정점 2가 정점 3과 같은 값을 공유하는 구조로 인해 기준에서 벗어나 제외됩니다.
풀이 접근 방식
이 문제는 DFS(깊이 우선 탐색)을 활용해 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재 탐색 경로 위에서 각 'x' 값이 몇 번 등장했는지 빈도 배열(frq)로 추적합니다.
- 정점에 진입할 때, 해당 정점의 'x' 값이 아직 경로에 한 번도 등장하지 않았다면(frq == 0) 그 정점을 슈퍼 꼭짓점으로 표시(chk = 1)합니다.
- 재귀 호출이 끝나고 되돌아올 때는 빈도를 다시 감소시켜(backtracking) 경로 상태를 정확하게 유지합니다.
단계별 알고리즘
크기가 100005인 배열 vertexVal, frq, chk를 선언한다.
크기가 200005인 배열 vcti를 선언한다.
함수 dfs(j, k)를 정의한다:
만약 frq[vertexVal[j]] == 0 이라면:
chk[j] := 1
frq[vertexVal[j]] 를 1 증가시킨다.
vcti[j]의 각 원소 a에 대해:
a가 k(부모 정점)와 같지 않다면:
dfs(a, j) 재귀 호출
frq[vertexVal[j]] 를 1 감소시킨다.
i := 0 부터 i < n 까지 반복:
vertexVal[i] := values[i]
i := 0 부터 i < n 까지 반복:
a := edges[i]의 첫 번째 값
b := edges[i]의 두 번째 값
vcti[a]의 끝에 b를 삽입
vcti[b]의 끝에 a를 삽입
dfs(1, 0) 호출
i := 1 부터 i <= n 까지 반복:
chk[i]가 0이 아니라면:
i를 출력C++ 구현 예제
더 나은 이해를 돕기 위해 실제 C++ 코드로 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int n;
int vertexVal[100005], frq[100005], chk[100005];
vector<int> vcti[200005];
void dfs(int j, int k){
if (frq[vertexVal[j]] == 0)
chk[j] = 1;
frq[vertexVal[j]]++;
for (auto a : vcti[j]) {
if (a != k)
dfs(a, j);
}
frq[vertexVal[j]]--;
}
void solve(int values[], vector<pair<int, int>> edges){
for (int i = 0; i < n; i++)
vertexVal[i] = values[i];
for (int i = 0; i < n; i++){
int a, b;
a = edges[i].first;
b = edges[i].second;
vcti[a].push_back(b);
vcti[b].push_back(a);
}
dfs(1, 0);
for (int i = 1;i <= n; i++){
if (chk[i]) cout<< i <<endl;
}
}
int main() {
n = 5;
int values[] = {1, 2, 2, 1, 3}; vector<pair<int, int>> edges = {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}};
solve(values, edges);
return 0;
}입력
5, {1, 2, 2, 1, 3}, {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}}출력
1 3 4 5
마무리
이 알고리즘은 DFS의 백트래킹 특성을 활용해 각 정점까지의 경로 정보를 O(n + m) 시간 복잡도로 효율적으로 관리합니다. 빈도 배열을 진입 시 증가하고 복귀 시 감소시키는 패턴은 그래프 탐색 문제에서 경로 상태를 추적할 때 널리 쓰이는 유용한 기법이므로, 꼭 익혀두시길 권장합니다.