문제 개요
이번 튜토리얼에서는 무방향 그래프(undirected graph)를 방향 그래프(directed graph)로 변환하되, 변환된 그래프에 길이가 1보다 큰 경로가 존재하지 않도록 만드는 방법을 C++로 구현해 봅니다.
여기서 '길이가 1보다 큰 경로가 없다'는 것은, 간선에 방향을 부여한 뒤 어떤 정점에서 출발하더라도 간선을 두 번 이상 연속해서 따라갈 수 없다는 의미입니다. 즉, 어느 정점에서 이동을 시작해도 한 번의 이동 후에는 반드시 더 나아갈 수 없는 정점에 도달해야 합니다.
접근 방식: 이분 그래프 판별
이 문제의 핵심은 이분 그래프(bipartite graph)입니다. 그래프의 모든 정점을 두 가지 색으로 칠하되 인접한 정점끼리는 서로 다른 색을 갖도록 할 수 있다면, 모든 간선을 한쪽 색 집합에서 다른 쪽 색 집합을 향하도록 일관되게 방향을 정하면 됩니다. 이렇게 하면 한쪽 집합의 정점에서만 나가는 간선이 존재하므로 어떤 경로도 길이 1을 초과할 수 없습니다.
반대로 그래프에 홀수 길이의 사이클이 포함되어 있다면, 즉 이분 그래프가 아니라면 어떻게 방향을 정하더라도 조건을 만족하는 것이 불가능합니다. 이 경우 -1을 출력합니다.
전체 알고리즘의 흐름은 다음과 같습니다.
- DFS를 수행하며 그래프를 2-색칠하고, 인접한 두 정점의 색이 같다면 이분 그래프가 아니라고 표시합니다.
- 이분 그래프가 아니면 -1을 출력하고 종료합니다.
- 이분 그래프라면 각 간선의 두 끝점 중 시작점이 지정된 색이 되도록 방향을 정해 출력합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
#define N 100005
// 그래프 저장
vector<int> gr[N];
// 각 정점의 색 저장
int colour[N];
vector<pair<int, int> > edges;
bool bip;
// 그래프에 간선 추가
void add_edge(int x, int y){
gr[x].push_back(y);
gr[y].push_back(x);
edges.push_back(make_pair(x, y));
}
// 주어진 그래프가
// 이분 그래프인지 확인
void dfs(int x, int col){
colour[x] = col;
// 자식 정점으로 이동
for (auto i : gr[x]) {
if (colour[i] == -1)
dfs(i, col ^ 1);
// 자식과 부모의 색이 같은 경우
else if (colour[i] == col)
bip = false;
}
}
// 방향 그래프로 변환
void convert_directed(int n, int m){
memset(colour, -1, sizeof colour);
bip = true;
// 이분 그래프 검사 함수 호출
dfs(1, 1);
if (!bip) {
cout << -1;
return;
}
// 이분 그래프인 경우 간선 방향 결정
for (int i = 0; i < m; i++) {
if (colour[edges[i].first] == 0)
swap(edges[i].first, edges[i].second);
cout << edges[i].first << " " << edges[i].second << endl;
}
}
int main(){
int n = 4, m = 3;
add_edge(1, 2);
add_edge(1, 3);
add_edge(1, 4);
convert_directed(n, m);
return 0;
}실행 결과
1 2 1 3 1 4
코드 동작 설명
예제 그래프에서 DFS는 정점 1을 색 1로 칠하고, 정점 2·3·4를 색 0으로 칠합니다. 간선 처리 시 first에 해당하는 정점의 색이 0이면 두 끝점을 서로 교환하여 방향을 정하기 때문에, 위 예제에서는 세 간선이 모두 "1 2", "1 3", "1 4" 형태로 출력됩니다.
결과적으로 정점 1에서 2, 3, 4로 향하는 간선만 존재하고, 정점 2·3·4에서는 나가는 간선이 전혀 없습니다. 따라서 어떤 정점에서 출발하더라도 경로의 길이가 1을 넘을 수 없으며, 문제의 조건이 충족됩니다.
이 알고리즘의 시간 복잡도는 DFS 탐색과 간선 순회에 비례하여 O(V + E)이며, 공간 복잡도 역시 그래프 저장에 필요한 O(V + E)입니다.