개념
하나의 그래프와 그래프 안의 특정 시작 정점(source), 그리고 숫자 k(여기서 k는 시작 정점과 도착 정점 사이의 경로 길이를 의미합니다)가 주어졌을 때, 주어진 시작 정점에서 출발하여 다른 임의의 정점(즉, 도착 정점)에서 끝나는 단순 경로(simple path, 사이클이 없는 경로)가 존재하는지 판별하는 것이 이 문제의 목표입니다.
문제 설명에 사용된 그래프는 다음과 같습니다.
입력 예시 1
Source s = 0, k = 64
출력 결과 1
True
위 입력의 경우 0 -> 7 -> 1 -> 2 -> 8 -> 6 -> 5 -> 3 -> 4 로 이어지는 단순 경로가 존재하며, 이 경로의 총 거리는 68km로 64보다 큽니다.
입력 예시 2
Source s = 0, k = 70
출력 결과 2
False
위 그래프에서 가장 긴 단순 경로의 거리는 69입니다(0 -> 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8). 따라서 69보다 큰 값이 입력으로 주어지면 출력은 항상 false가 됩니다.
접근 방법
먼저 주의해야 할 중요한 점이 있습니다. 단순히 BFS(너비 우선 탐색)나 DFS(깊이 우선 탐색)를 수행하면서 매 단계마다 가장 긴 간선만 선택하는 방식으로는 이 문제를 해결할 수 없습니다. 그 이유는 짧은 간선을 거쳐도 그 뒤에 연결된 가중치가 큰 간선들 덕분에 결과적으로 더 긴 경로가 만들어질 수 있기 때문입니다.
따라서 이 문제는 백트래킹(Backtracking) 기법을 활용해야 합니다. 구체적인 동작 방식은 다음과 같습니다.
- 주어진 시작 정점에서 출발하여 현재 정점으로부터 갈 수 있는 모든 경로를 탐색합니다.
- 탐색 과정에서 시작 정점으로부터의 현재 거리를 계속 추적합니다.
- 거리가 k보다 커지면 true를 반환합니다.
- 어떤 경로가 k보다 큰 거리를 만들지 못하는 경우에는 백트래킹하여 다른 경로를 시도합니다.
그렇다면 경로가 단순(simple)하다는 것, 즉 사이클에 빠져 무한히 반복하지 않는다는 것은 어떻게 보장할 수 있을까요? 핵심은 현재 경로에 포함된 정점들을 배열에 기록해 두는 것입니다. 새로운 정점을 경로에 추가할 때마다 해당 정점이 이미 현재 경로에 존재하는지 검사하고, 이미 존재한다면 그 간선은 무시합니다.
구현 예제
// 가중치가 k보다 큰 단순 경로가 존재하는지 찾는 프로그램
#include<bits/stdc++.h>
using namespace std;
// iPair ==> 정수 쌍(Integer Pair)
typedef pair<int, int> iPair;
// 인접 리스트 표현 방식으로 가중 그래프를 나타내는 클래스
class Graph{
int V1; // 정점의 개수
// 가중 그래프에서는 모든 간선에 대해 정점과 가중치 쌍을 저장해야 함
list< pair<int, int>> *adj1;
bool pathMoreThanKUtil(int src1, int k, vector<bool>&path1);
public:
Graph(int V1); // 생성자
// 그래프에 간선을 추가하는 함수
void addEdge(int u1, int v1, int w1);
bool pathMoreThanK(int src1, int k);
};
// 그래프에 k보다 긴 경로가 존재하면 true를 반환
bool Graph::pathMoreThanK(int src1, int k){
// 아무것도 포함되지 않은 경로 배열 생성
vector<bool> path1(V1, false);
// 시작 정점을 경로에 추가
path1[src1] = 1;
return pathMoreThanKUtil(src1, k, path1);
}
// src에서 출발하는 모든 경로를 재귀적으로 탐색하는 유틸리티 함수
bool Graph::pathMoreThanKUtil(int src1, int k, vector<bool>&path1){
// k가 0 이하이면 true 반환
if (k <= 0)
return true;
// 시작 정점 src의 모든 인접 정점을 가져와
// src로부터의 모든 경로를 재귀적으로 탐색
list<iPair>::iterator i;
for (i = adj1[src1].begin(); i != adj1[src1].end(); ++i){
// 인접 정점과 간선의 가중치를 가져옴
int v1 = (*i).first;
int w1 = (*i).second;
// 정점 v가 이미 경로에 있다면 사이클이 존재하는 것이므로
// 해당 간선은 무시
if (path1[v1] == true)
continue;
// 간선의 가중치가 k보다 크거나 같으면 true 반환
if (w1 >= k)
return true;
// 그렇지 않으면 이 정점을 경로에 추가
path1[v1] = true;
// 이 인접 정점을 통해 k보다 긴 경로를 만들 수 있다면 true 반환
if (pathMoreThanKUtil(v1, k-w1, path1))
return true;
// 백트래킹
path1[v1] = false;
}
// 어떤 인접 정점으로도 더 긴 경로를 만들 수 없으면 false 반환
return false;
}
// 인접 리스트를 위한 메모리 할당
Graph::Graph(int V1){
this->V1 = V1;
adj1 = new list<iPair> [V1];
}
// 가중치 w를 가지는 간선 (u, v)를 추가하는 유틸리티 함수
void Graph::addEdge(int u1, int v1, int w1){
adj1[u1].push_back(make_pair(v1, w1));
adj1[v1].push_back(make_pair(u1, w1));
}
// Graph 클래스의 메서드를 테스트하기 위한 드라이버 프로그램
int main(){
// 위 그림에 제시된 그래프 생성
int V1 = 9;
Graph g(V1);
// 위에서 보여준 그래프 구성
g.addEdge(0, 1, 5);
g.addEdge(0, 7, 9);
g.addEdge(1, 2, 9);
g.addEdge(1, 7, 12);
g.addEdge(2, 3, 8);
g.addEdge(2, 8, 3);
g.addEdge(2, 5, 10);
g.addEdge(3, 4, 10);
g.addEdge(3, 5, 15);
g.addEdge(4, 5, 11);
g.addEdge(5, 6, 3);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 7);
g.addEdge(7, 8, 8);
int src1 = 0;
int k = 70;
g.pathMoreThanK(src1, k)? cout << "Yes\n" :
cout << "No\n";
k = 68;
g.pathMoreThanK(src1, k)? cout << "Yes\n" :
cout << "No\n";
return 0;
}실행 결과
No Yes