C++에서 주어진 부분 수열 목록으로부터 원본 수열을 유일하게 재구성할 수 있는지 판별하는 방법을 알아봅니다. 이 문제는 방향 그래프의 위상 정렬(topological sort)을 활용하면 깔끔하게 해결할 수 있으며, 그래프 이론과 알고리즘 설계 능력을 동시에 점검할 수 있는 대표적인 문제입니다.
문제 개요
원본 수열 org가 seqs에 담긴 여러 수열로부터 유일하게 재구성될 수 있는지 확인하는 것이 목표입니다. 원본 수열은 1부터 n까지의 정수로 이루어진 순열(permutation)이며, n의 범위는 1 ≤ n ≤ 10⁴입니다. 여기서 '재구성'이란 seqs의 모든 수열을 포함하는 최단 공통 초수열(shortest common supersequence)을 만드는 것을 의미합니다. 즉, seqs로부터 재구성 가능한 수열이 오직 하나뿐이고, 그것이 바로 원본 수열 org와 일치하는지 검사해야 합니다.
예시로 이해하기
예를 들어 org = [1,2,3], seqs = [[1,2],[1,3]]이라면 결과는 false입니다. [1,2,3]만 재구성 가능한 것이 아니라 [1,3,2] 역시 조건을 만족하는 유효한 수열이기 때문입니다. 반대로 seqs가 [[1,2],[2,3]]라면 1 → 2 → 3 순서가 강제되므로 유일하게 [1,2,3]만 재구성할 수 있습니다.
해결 전략: 위상 정렬 활용
핵심 아이디어는 다음과 같습니다.
- seqs의 각 수열에서 인접한 두 원소 (u, v)마다 u → v 간선을 추가합니다.
- 각 노드의 진입 차수(indegree)를 계산합니다.
- 진입 차수가 0인 노드를 큐에 넣고 위상 정렬을 진행하되, 매 단계에서 큐에 노드가 정확히 하나만 존재해야 다음 순서가 유일하다고 판단할 수 있습니다.
- 정렬 과정에서 선택지가 둘 이상 생기거나, 결과가 org와 일치하지 않으면 false를 반환합니다.
알고리즘 단계
- 두 벡터가 완전히 같은지 비교하는 헬퍼 함수 ok()를 정의합니다. 크기가 다르거나 임의의 위치에서 값이 다르면 false를 반환합니다.
- n := org의 크기로 설정하고, 크기가 (n+1)인 그래프 배열, 진입 차수를 저장할 맵(indegree), 인덱스 변수 idx = 0을 준비합니다.
- seqs의 각 수열을 순회하면서 첫 번째 원소가 1~n 범위 안에 있는지 검사하고, 인접한 원소 쌍 (u, v)로 간선을 만들어 그래프에 추가한 뒤 indegree[v]를 1 증가시킵니다. 값이 범위를 벗어나면 즉시 false를 반환합니다.
- indegree에 등록된 노드 중 진입 차수가 0인 노드를 모두 큐에 삽입합니다.
- 큐가 빌 때까지 반복합니다. 이때 큐의 크기가 1보다 크면 순서가 유일하지 않으므로 false를 반환하고, idx가 이미 org의 크기에 도달했는데도 큐에 요소가 남아 있으면 역시 false를 반환합니다.
- 큐에서 노드를 꺼내 org[idx]와 비교하고, 일치하지 않으면 false를 반환한 후 idx를 1 증가시킵니다.
- 현재 노드의 인접 노드들의 진입 차수를 감소시키고, 진입 차수가 0이 된 노드는 큐에 삽입합니다.
- 모든 과정이 끝난 뒤 idx가 org의 크기와 같으면 true를 반환합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(vector<int>& v1, vector<int>& v2){
if (v1.size() != v2.size())
return false;
for (int i = 0; i < v1.size(); i++) {
if (v1[i] != v2[i])
return false;
}
return true;
}
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs){
int n = org.size();
vector<int> graph[n + 1];
unordered_map<int, int> indegree;
int idx = 0;
for (int i = 0; i < seqs.size(); i++) {
if (seqs[i].size() >= 1 && (seqs[i][0] > n || seqs[i][0] < 1))
return false;
if (seqs[i].size() >= 1 && !indegree.count(seqs[i][0])) {
indegree[seqs[i][0]] = 0;
}
for (int j = 1; j < seqs[i].size(); j++) {
int u = seqs[i][j - 1];
int v = seqs[i][j];
graph[u].push_back(v);
indegree[v]++;
if (u > n || v > n || u < 1 || v < 1)
return false;
}
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (indegree.count(i) && indegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
if (q.size() > 1) {
return false;
}
if (idx == org.size()) {
return false;
}
int node = q.front();
q.pop();
if (org[idx] != node) {
return false;
}
idx++;
for (int i = 0; i < graph[node].size(); i++) {
int v = graph[node][i];
indegree[v]--;
if (indegree[v] == 0) {
q.push(v);
}
}
}
return idx == org.size();
}
};
main(){
Solution ob;
vector<int> v = {1,2,3};
vector<vector<int>> v1 = {{1,2},{1,3}};
cout << (ob.sequenceReconstruction(v, v1));
}실행 결과
입력:
{1,2,3}, {{1,2},{1,3}}출력:
0
출력이 0(false)인 이유는 앞서 살펴본 것처럼 [1,2,3]과 [1,3,2] 두 가지 수열이 모두 재구성 가능하여 유일성이 깨지기 때문입니다.
복잡도 분석
- 시간 복잡도: O(V + E) — 모든 노드와 간선을 한 번씩만 처리합니다. 여기서 V는 노드 수(n), E는 seqs에 포함된 인접 쌍의 총 개수입니다.
- 공간 복잡도: O(V + E) — 그래프 인접 리스트와 진입 차수 맵, 큐에 필요한 저장 공간입니다.
마무리
이 문제의 핵심은 '유일성'을 어떻게 검증하느냐입니다. 위상 정렬을 수행하면서 매 단계 큐에 들어 있는 노드가 정확히 하나인지만 확인하면, 다음에 올 원소가 항상 하나로 결정되는지 손쉽게 판별할 수 있습니다. 그래프 탐색과 정렬 알고리즘을 응용하는 좋은 연습 문제이므로, 직접 코드를 작성하며 다양한 입력 케이스(빈 seqs, 중복 간선, 범위를 벗어나는 값 등)도 함께 테스트해 보시기 바랍니다.