그래프 알고리즘(2) - 벨만포드, 존슨, 코사리주 알고리즘

1. 최단 경로 문제 다시 살펴보기

• 다익스트라 알고리즘은 성능 면에서 우수하나, 모든 그래프에 적용 불가능
• 그래프에 음수 가중치가 있을 경우 최적의 경로를 찾지 못하는 경우 발생

2. 벨만-포드 알고리즘

• 그래프의 모든 엣지에 대해 다익스트라의 그리디 선택 방법을 반복하여 점진적인 최단 거리 탐색

1) 연습 문제 32: 벨만-포드 알고리즘 구현하기

#include<vector>
#include<iostream>
#include<climits>

using namespace std;

struct Edge
{
	int src;
	int dst;
	int weight;
};

const int UNKNOWN = INT_MAX;

vector<int> BellmanFord(vector<Edge> edges, int V, int start)
{
	vector<int> distance(V, UNKNOWN);
	distance[start]=0;
	for(int i=0;i<V;i++)
	{
		for(auto& e : edges)
		{
			if(distance[e.src] == UNKNOWN)
				continue;
			if(distance[e.dst]>distance[e.src]+e.weight)
				distance[e.dst]=distance[e.src]+e.weight;
		}
	}
	return distance;
}

int main()
{
	int V = 5;
	vector<Edge> edges;
	vector<vector<int>> edge_map{
		{0,1,3},
		{1,2,5},
		{1,3,10},
		{3,2,-7},
		{2,4,2}
	};
	for(auto& e : edge_map)
	{
		edges.emplace_back(Edge {e[0], e[1], e[2]});
	}
	int start = 0;
	vector<int> distance = BellmanFord(edges, V, start);

	cout<<"["<<start<<"번 정점으로부터 최소 거리]"<<endl;
	for(int i=0;i<distance.size();i++)
	{
		if(distance[i] == UNKNOWN)
			cout<<i<<"번 정점 : 방문하지 않음"<<endl;
		else
			cout<<i<<"번 정점: "distance[i]<<endl;
	}
}

3. 벨만-포드 알고리즘과 음수 가중치 사이클

1) 연습 문제 33: 음수 가중치 사이클 찾기

#include <vector>
#include <iostream>
#include <climits>

using namespace std;

struct Edge
{
	int src;
	int dst;
	int weight;
};

const int UNKNOWN = INT_MAX;

vector<int> BellmanFord(vector<Edge> edges, int V, int start)
{
	vector<int> distance(V, UNKNOWN);
	distance[start] = 0;

	// (V - 1)번 반복
	for (int i = 0; i < V - 1; i++)
	{
		// 전체 에지에 대해 반복
		for (auto& e : edges)
		{
			// 에지의 시작 정점의 거리 값이 UNKNOWN이면 스킵
			if (distance[e.src] == UNKNOWN)
				continue;

			// 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
			// 거리 값을 업데이트함.
			if (distance[e.dst] > distance[e.src] + e.weight)
			{
				distance[e.dst] = distance[e.src] + e.weight;
			}
		}
	}

	// 음수 가중치 사이클이 있는 지 검사
	for (auto& e : edges)
	{
		if (distance[e.src] == UNKNOWN)
			continue;

		if (distance[e.dst] > distance[e.src] + e.weight)
		{
			cout << "음수 가중치 사이클 발견!" << endl;
			return {};
		}
	}

	return distance;
}

int main()
{
	int V = 6;              // 정점 개수
	vector<Edge> edges;     // 에지 포인터의 벡터

	vector<vector<int>> edge_map { // {시작 정점, 목표 정점, 가중치}
		{0, 1, 3},
		{1, 3, -8},
		{2, 1, 3},
		{2, 5, 5},
		{3, 2, 3},
		{2, 4, 2},
		{4, 5, -1},
		{5, 1, 8}
	};

	for (auto& e : edge_map)
	{
		edges.emplace_back(Edge {e[0], e[1], e[2]});
	}

	int start = 0;
	vector<int> distance = BellmanFord(edges, V, start);

	if (!distance.empty())
	{
		cout << "[" << start << "번 정점으로부터 최소 거리]" << endl;

		for (int i = 0; i < distance.size(); i++)
		{
			if (distance[i] == UNKNOWN)
				cout << i << "번 정점: 방문하지 않음!" << endl;
			else
				cout << i << "번 정점: " << distance[i] << endl;
		}
	}
}

2) 실습 문제 15: 욕심쟁이 로봇

#include <vector>
#include <iostream>
#include <climits>
#include <fstream>

using namespace std;

struct Edge
{
	int src;
	int dst;
	int weight;
};

const int UNKNOWN = INT_MAX;

bool ReadTestCase(string filename, int& N, vector<Edge>& edges)
{
	ifstream infile(filename);

	if (!infile.is_open())
	{
		cout << "테스트 케이스 파일을 열 수 없습니다!" << endl;
		return false;
	}

	infile >> N;

	for (int i = 0; i < N * N - 1; i++)
	{
		string directions;
		int power;

		infile >> directions >> power;

		int next = i;

		for (auto d : directions)
		{

			switch (d)
			{
			case 'N': next = i - N; break;
			case 'E': next = i + 1; break;
			case 'S': next = i + N; break;
			case 'W': next = i - 1; break;
			}

			// power 값의 부호를 바꿔서 에지 가중치로 사용
			edges.push_back(Edge {i, next, -power});
		}
	}

	return true;
}

vector<int> BellmanFord(vector<Edge> edges, int V, int start)
{
	vector<int> distance(V, UNKNOWN);
	distance[start] = 0;

	// (V - 1)번 반복
	for (int i = 0; i < V - 1; i++)
	{
		// 전체 에지에 대해 반복
		for (auto& e : edges)
		{
			// 에지의 시작 정점의 거리 값이 UNKNOWN이면 스킵
			if (distance[e.src] == UNKNOWN)
				continue;

			// 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
			// 거리 값을 업데이트함.
			if (distance[e.dst] > distance[e.src] + e.weight)
			{
				distance[e.dst] = distance[e.src] + e.weight;
			}
		}
	}

	// 음수 가중치 사이클이 있는 지 검사
	for (auto& e : edges)
	{
		if (distance[e.src] == UNKNOWN)
			continue;

		if (distance[e.dst] > distance[e.src] + e.weight)
		{
			//cout << "음수 가중치 사이클 발견!" << endl;
			return {};
		}
	}

	return distance;
}

int main()
{
	int N;
	vector<Edge> edges;     // 에지 리스트

	// testcase1~5.txt 파일로부터 테스트 입력을 받아 결과 확인
	if (ReadTestCase("testcase1.txt", N, edges))
	{
		vector<int> distance = BellmanFord(edges, N * N, 0);

		if (distance.empty() || distance[N * N - 1] == UNKNOWN)
			cout << "탐색 중단" << endl;
		else
			cout << -1 * distance[N * N - 1] << endl;
	}
}

4. 존슨 알고리즘

1) 존슨 알고리즘

• 다익스트라 알고리즘의 효율성을 활용함과 동시에 음수 가중치를 갖는 그래프에 대해서도 올바른 결과 생성 가능
• 전체 에지 가중치를 음수가 아닌 형태로 변환
• 그래프에 새로운 ‘더미’정점을 추가
• 더미 정점과 나머지 모든 정점 사이에 가중치가 0인 에지를 연결
• 벨만-포드 알고리즘을 이용하여 더미 정점과 나머지 정점들 사이에 최단 경로를 찾고 각 정점까지의 최단 거리 기록

2) 연습 문제 34: 존슨 알고리즘 구현하기

#include <vector>
#include <iostream>
#include <climits>

using namespace std;

struct Edge
{
	int src;
	int dst;
	int weight;
};

const int UNKNOWN = INT_MAX;

bool HasNegativeCycle(const vector<Edge>& edges, vector<int> distance)
{
	for (auto& e : edges)
	{
		if (distance[e.src] == UNKNOWN)
			continue;

		if (distance[e.dst] > distance[e.src] + e.weight)
			return true;
	}

	return false;
}

vector<int> BellmanFord(vector<Edge> edges, int V)
{
	vector<int> distance(V + 1, UNKNOWN);

	int s = V;
	for (int i = 0; i < V; i++)
	{
		edges.push_back(Edge {s, i, 0});
	}

	distance[s] = 0;

	// 정점 개수가 V + 1개 이므로 V번 반복
	for (int i = 0; i < V; i++)
	{
		for (auto& e : edges)
		{
			// 에지의 시작 정점의 거리 값이 UNKNOWN이면 스킵
			if (distance[e.src] == UNKNOWN)
				continue;

			// 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
			// 거리 값을 업데이트함.
			if (distance[e.dst] > distance[e.src] + e.weight)
			{
				distance[e.dst] = distance[e.src] + e.weight;
			}
		}
	}

	// 음수 가중치 사이클이 있는 지 검사
	if (HasNegativeCycle(edges, distance))
	{
		cout << "음수 가중치 사이클 발견!" << endl;
		return {};
	}

	return distance;
}

int GetMinDistance(vector<int>& distance, vector<bool>& visited)
{
	int minDistance = UNKNOWN;
	int minIndex = -1;

	for (int i = 0; i < distance.size(); i++)
	{
		if (!visited[i] && distance[i] <= minDistance)
		{
			minDistance = distance[i];
			minIndex = i;
		}
	}

	return minIndex;
}

vector<int> Dijkstra(vector<Edge> edges, int V, int start)
{
	vector<int> distance(V, UNKNOWN);
	vector<bool> visited(V, false);

	distance[start] = 0;

	for (int i = 0; i < V - 1; i++)
	{
		// 방문하지 않은 정점 중에서 최소 거리 정점을 찾음
		int curr = GetMinDistance(distance, visited);

		visited[curr] = true;

		for (auto& e : edges)
		{
			// 인접한 정점만 고려
			if (e.src != curr)
				continue;

			// 이미 방문했으면 무시
			if (visited[e.dst])
				continue;

			if (distance[curr] != UNKNOWN &&
				distance[e.dst] > distance[curr] + e.weight)
			{
				distance[e.dst] = distance[curr] + e.weight;
			}
		}
	}

	return distance;
}

void Johnson(vector<Edge> edges, int V)
{
	// 더미 정점을 추가한 그래프에서 최단 거리를 계산
	vector<int> h = BellmanFord(edges, V);

	if (h.empty())
		return;

	// 에지 가중치 재설정
	for (auto& e : edges)
	{
		e.weight += (h[e.src] - h[e.dst]);
	}

	// 모든 정점들 사이의 최단 거리를 저장
	vector<vector<int>> shortest(V);

	for (int i = 0; i < V; i++)
	{
		shortest[i] = Dijkstra(edges, V, i);
	}

	// 가중치 변환 수식을 역으로 적용하여 최단 거리를 출력
	for (int i = 0; i < V; i++)
	{
		cout << i << ":\\n";

		for (int j = 0; j < V; j++)
		{
			if (shortest[i][j] != UNKNOWN)
			{
				shortest[i][j] += h[j] - h[i];

				cout << "\\t" << j << ": " << shortest[i][j] << endl;
			}
		}
	}
}

int main()
{
	int V = 5;              // 정점 개수
	vector<Edge> edges;     // 에지 포인터의 벡터

	vector<vector<int>> edge_map { // {시작 정점, 목표 정점, 가중치}
		{0, 1, -7},
		{1, 2, -2},
		{2, 0, 10},
		{0, 3, -5},
		{0, 4, 2},
		{3, 4, 4}
	};

	for (auto& e : edge_map)
	{
		edges.emplace_back(Edge {e[0], e[1], e[2]});
	}

	Johnson(edges, V);
}

3) 실습 문제 16: 무작위 통계 그래프

#include <vector>
#include <iostream>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <queue>

using namespace std;

struct Edge
{
	int src;
	int dst;
	int weight;
};

const int UNKNOWN = 1e9;

static unsigned long int next_random = 1;

int rand(void)
{
	next_random = next_random * 1103515245 + 12345;
	return (unsigned int)(next_random / 65536) % 32768;
}

void srand(unsigned int seed)
{
	next_random = seed;
}

enum RESULT
{
	VALID,
	INVALID,
	INTERESTING
};

struct Graph
{
	int V, E;
	int maxWeight = -UNKNOWN;

	vector<Edge> edges;
	vector<vector<int>> adj;
	vector<vector<int>> weight;

	Graph(int v, int e) : V(v), E(e)
	{
		vector<vector<bool>> used(V, vector<bool>(V, false));

		adj.resize(V);
		weight.resize(V, vector<int>(V, UNKNOWN));

		while (e)
		{
			// 에지 정보 생성
			int u = rand() % V;
			int v = rand() % V;
			int w = rand() % 100;

			if (rand() % 3 == 0)
			{
				w = -w;
			}

			// 유효한 에지인지 확인
			if (u == v || used[u][v])
				continue;

			// 에지 정보를 추가하고 used 배열 값을 설정
			edges.push_back(Edge {u, v, w});
			adj[u].push_back(v);
			weight[u][v] = w;
			maxWeight = max(maxWeight, w);

			used[u][u] = used[v][v] = used[u][v] = used[v][u] = true;
			e--;
		}

		for (int i = 0; i < V; i++)
		{
			// 유효하지 않은 그래프에 대해 V 값을 -1로 설정
			if (!used[i][i])
			{
				V = -1;
				break;
			}
		}
	}
};

vector<int> BellmanFord(Graph G)
{
	vector<int> distance(G.V + 1, UNKNOWN);

	int s = G.V;

	for (int i = 0; i < G.V; i++)
	{
		G.edges.push_back(Edge {s, i, 0});
	}

	distance[s] = 0;

	// 정점 개수가 V + 1개 이므로 V번 반복
	for (int i = 0; i <= G.V; i++)
	{
		for (auto& e : G.edges)
		{
			if (distance[e.src] == UNKNOWN)
				continue;

			if (distance[e.dst] > distance[e.src] + e.weight)
			{
				distance[e.dst] = distance[e.src] + e.weight;
			}
		}
	}

	for (auto& e : G.edges)
	{
		if (distance[e.src] == UNKNOWN)
			continue;

		if (distance[e.dst] > distance[e.src] + e.weight)
		{
			return {};
		}
	}

	return distance;
}

vector<int> Dijkstra(int src, Graph G)
{
	using State = pair<int, int>;  // {distance, id}

	priority_queue<State, vector<State>, greater<State>> heap;
	vector<bool> visited(G.V, false);
	vector<int> distance(G.V, UNKNOWN);

	heap.push({0, src});
	distance[src] = 0;

	while (!heap.empty())
	{
		State top = heap.top();
		heap.pop();

		int dist = top.first;
		int node = top.second;

		visited[node] = true;

		for (auto next : G.adj[node])
		{
			if (visited[next])
			{
				continue;
			}
			
			if (dist != UNKNOWN && distance[next] > dist + G.weight[node][next])
			{
				distance[next] = dist + G.weight[node][next];

				heap.push({distance[next], next});
			}
		}
	}
	
	return distance;
}

RESULT TestGraph(Graph G)
{
	if (G.V == -1)
		return INVALID;

	vector<int> distance = BellmanFord(G);

	if (distance.empty())
		return VALID;

	for (auto& e : G.edges)
	{
		G.weight[e.src][e.dst] += (distance[e.src] - distance[e.dst]);
	}

	double result = 0;

	for (int i = 0; i < G.V; i++)
	{
		vector<int> shortest = Dijkstra(i, G);

		double average = 0;
		int count = 0;

		for (int j = 0; j < G.V; j++)
		{
			if (i == j || shortest[j] == UNKNOWN)
				continue;

			shortest[j] += (distance[j] - distance[i]);
			average += shortest[j];
			count++;
		}

		average = average / count;
		result += average;
	}

	result = result / G.V;

	double ratio = result / G.maxWeight;

	return (ratio < 0.5) ? INTERESTING : VALID;
}

int main()
{
	long seed;
	int iterations, V, E;

	cin >> seed;
	cin >> iterations;
	cin >> V >> E;

	int invalid = 0;
	int valid = 0;
	int interesting = 0;

	srand(seed);

	while (iterations--)
	{
		Graph G(V, E);

		switch (TestGraph(G))
		{
		case INVALID: invalid++; break;
		case VALID: valid++; break;
		case INTERESTING:
		{
			valid++;
			interesting++;
			break;
		}
		}
	}

	double percentInteresting = (double)interesting / valid * 100;

	cout << "유효하지 않은 그래프 개수: " << invalid << endl;
	cout << "흥미로운 그래프 생성 비율: " << fixed << setprecision(2) << percentInteresting << "%" << endl;

	return 0;
}

/*
42 1000 15 10
유효하지 않은 그래프 개수: 996
흥미로운 그래프 생성 비율: 0.00%

11111 400 5 5
유효하지 않은 그래프 개수: 55
흥미로운 그래프 생성 비율: 0.58%
*/

5. 강한 연결 요소

1) 방향 그래프를 통한 연결 요소

• 채널을 구독하는 사람들 그룹의 유사성을 찾기가 어려운 부분을
• 방향 그래프의 공통적인 특징을 통해 문제 해결 가능

2) 방향 그래프와 무방향 그래프에서 연결성

• 무방향 그래프에서 연결 요소란 모든 정점이 서로 연결되어 있는 부분 그래프 중에서 최대 크기 부분 그래프 집합을 의미
• 모든 정점이 연결되어 있을 경우 단일 연결 요소로 구성
• ‘강한’ 연결성의 경우 방향 그래프에서만 존재
• 강한 연결 요소는 그래프 내에서 다른 부분 그래프와 단절되어 있을 필요 X ( 경로 존재 가능 )

6. 코사리주 알고리즘

1) 코사리주 알고리즘

• 그래프에서 강한 연결 요소를 찾는 방법
• DFS를 두 번 수행 ( 첫 번째는 입력 그래프 자체, 두 번째는 입력 그래프를 전치하여 수행 )
• 그래프 전치 : 원본 그래프에서 시작 정점과 목표 정점이 서로 뒤바뀐 형태 / 엣지의 방향도 반대

2) 연습 문제 35: 코사리주 알고리즘 구현하기

#include <vector>
#include <stack>
#include <iostream>

using namespace std;

void FillStack(int node, vector<bool>& visited,
	vector<vector<int>>& adj, stack<int>& stack)
{
	visited[node] = true;

	for (auto next : adj[node])
	{
		if (!visited[next])
		{
			FillStack(next, visited, adj, stack);
		}
	}

	stack.push(node);
}

void CollectConnectedComponents(int node, vector<bool>& visited,
	vector<vector<int>>& adj, vector<int>& component)
{
	visited[node] = true;
	component.push_back(node);

	for (auto next : adj[node])
	{
		if (!visited[next])
		{
			CollectConnectedComponents(next, visited, adj, component);
		}
	}
}

vector<vector<int>> Transpose(int V, vector<vector<int>> adj)
{
	vector<vector<int>> transpose(V);

	for (int i = 0; i < V; i++)
	{
		for (auto next : adj[i])
		{
			transpose[next].push_back(i);
		}
	}

	return transpose;
}

vector<vector<int>> Kosaraju(int V, vector<vector<int>> adj)
{
	vector<bool> visited(V, false);
	stack<int> stack;

	for (int i = 0; i < V; i++)
	{
		if (!visited[i])
		{
			FillStack(i, visited, adj, stack);
		}
	}

	vector<vector<int>> transpose = Transpose(V, adj);

	fill(visited.begin(), visited.end(), false);

	vector<vector<int>> connectedComponents;

	while (!stack.empty())
	{
		int node = stack.top();
		stack.pop();

		if (!visited[node])
		{
			vector<int> component;

			CollectConnectedComponents(node, visited, transpose, component);
			connectedComponents.push_back(component);
		}
	}

	return connectedComponents;
}

int main()
{
	int V = 9;

	vector<vector<int>> adj =
	{
		{ 1, 3 },
		{ 2, 4 },
		{ 3, 5 },
		{ 7 },
		{ 2 },
		{ 4, 6 },
		{ 7, 2 },
		{ 8 },
		{ 3 }
	};

	vector<vector<int>> connectedComponents = Kosaraju(V, adj);

	cout << "강한 연결 요소 개수: " << connectedComponents.size() << endl;

	for (int i = 0; i < connectedComponents.size(); i++)
	{
		cout << "[" << i + 1 << "] ";

		for (auto node : connectedComponents[i])
			cout << node << " ";

		cout << endl;
	}
}

3) 실습 문제 17: 미로-순간이동 게임

#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
#include <climits>
#include <fstream>

using namespace std;

struct Edge
{
	int src;
	int dst;
	int weight;
};

const int UNKNOWN = INT_MAX;

bool ReadTestCase(string filename, int& V, vector<Edge>& edges)
{
	ifstream infile(filename);

	if (!infile.is_open())
	{
		cout << "테스트 케이스 파일을 열 수 없습니다!" << endl;
		return false;
	}

	int E;
	infile >> V >> E;

	for (int i = 0; i < E; i++)
	{
		int u, v, w;
		infile >> u >> v >> w;

		edges.push_back(Edge {u, v, w});
	}

	return true;
}

void FillStack(int node, vector<bool>& visited,
	vector<vector<int>>& adj, stack<int>& stack)
{
	visited[node] = true;

	for (auto next : adj[node])
	{
		if (!visited[next])
		{
			FillStack(next, visited, adj, stack);
		}
	}

	stack.push(node);
}

vector<bool> isStuck;
vector<int> inComponent;
int componentIndex;

void CollectConnectedComponents(int node, vector<bool>& visited,
	vector<vector<int>>& adj, vector<int>& component)
{
	visited[node] = true;
	component.push_back(node);

	inComponent[node] = componentIndex;

	for (auto next : adj[node])
	{
		if (!visited[next])
		{
			CollectConnectedComponents(next, visited, adj, component);
		}
		else if (inComponent[node] != inComponent[next])
		{
			isStuck[inComponent[next]] = false;
		}
	}
}

vector<vector<int>> Transpose(int V, vector<vector<int>> adj)
{
	vector<vector<int>> transpose(V);

	for (int i = 0; i < V; i++)
	{
		for (auto next : adj[i])
		{
			transpose[next].push_back(i);
		}
	}

	return transpose;
}

vector<vector<int>> Kosaraju(int V, vector<vector<int>> adj)
{
	isStuck.resize(V, true);
	inComponent.resize(V, UNKNOWN);
	componentIndex = 0;

	vector<bool> visited(V, false);
	stack<int> stack;

	for (int i = 0; i < V; i++)
	{
		if (!visited[i])
		{
			FillStack(i, visited, adj, stack);
		}
	}

	vector<vector<int>> transpose = Transpose(V, adj);

	fill(visited.begin(), visited.end(), false);

	vector<vector<int>> connectedComponents;

	while (!stack.empty())
	{
		int node = stack.top();
		stack.pop();

		if (!visited[node])
		{
			vector<int> component;

			CollectConnectedComponents(node, visited, transpose, component);
			connectedComponents.push_back(component);
			componentIndex++;
		}
	}

	return connectedComponents;
}

bool HasNegativeCycle(const vector<Edge>& edges, vector<int> distance)
{
	for (auto& e : edges)
	{
		if (distance[e.src] == UNKNOWN)
			continue;

		if (distance[e.dst] > distance[e.src] + e.weight)
			return true;
	}

	return false;
}

int BellmanFord(vector<Edge> edges, int V, int start)
{
	vector<int> distance(V, UNKNOWN);
	distance[start] = 0;

	// (V - 1)번 반복
	for (int i = 0; i < V - 1; i++)
	{
		// 전체 에지에 대해 반복
		for (auto& e : edges)
		{
			// 에지의 시작 정점의 거리 값이 UNKNOWN이면 스킵
			if (distance[e.src] == UNKNOWN)
				continue;

			// 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
			// 거리 값을 업데이트함.
			if (distance[e.dst] > distance[e.src] + e.weight)
			{
				distance[e.dst] = distance[e.src] + e.weight;
			}
		}
	}

	// 음수 가중치 사이클이 있으면 UNKNOWN 반환
	if (HasNegativeCycle(edges, distance))
	{
		return UNKNOWN;
	}

	int result = UNKNOWN;

	for (int i = 0; i < V; i++)
	{
		if (i == start) continue;

		result = min(result, distance[i]);
	}

	return result;
}

int main()
{
	int V;
	vector<Edge> edges;

	ReadTestCase("testcase7.txt", V, edges);

	vector<vector<int>> adj(V + 1);

	for (auto& e : edges)
	{
		adj[e.src].push_back(e.dst);
	}

	vector<int> results;

	for (int i = 0; i < V; i++)
	{
		if (adj[i].empty())
		{
			results.push_back(UNKNOWN);
			continue;
		}

		int shortest = BellmanFord(edges, V, i);

		if (shortest == UNKNOWN)
		{
			cout << "유효하지 않은 미로" << endl;
			return 0;
		}

		results.push_back(shortest);
	}

	for (int i = 0; i < V; i++)
	{
		if (results[i] == UNKNOWN)
			cout << i << ": 고립된 방" << endl;
		else
			cout << i << ": " << results[i] << endl;
	}

	auto components = Kosaraju(V, adj);

	for (int i = 0; i < components.size(); i++)
	{
		if (isStuck[i])
		{
			for (auto node : components[i])
			{
				cout << node << " ";
			}

			cout << endl;
		}
	}
}

7. 적절한 방법 선택하기

• 그래프 구조 구현에 있어 하나의 ‘완벽한’ 방법이 존재하지 않음
• 그래프 이론과 구현 방법에 대해 다음을 기억
  • 새로운 알고리즘 구현 시 ‘복사&붙여넣기’ 지양
  • 새로운 기능 추가시 추상적이거나 상황을 고려하지 않은 구현은 주의
  • 기본 목적 및 목적 달성을 위해 필요한 기능이 무엇인지
  • 주어진 문제와 연관된 정보를 나타내는 데 필요한 가장 기본적인 구성요소 파악
• 지속적인 연습을 통해 프로그래밍 실력을 늘리고 웹 검색을 통해 여러 방법도 파악해 보는 등 노력을 기울이자

 

출처 : 코딩 테스트를 위한 자료 구조와 알고리즘 with C++ (길벗)