[백준/BOJ] 백준 12880번 : 그래프 차이 최소

https://www.acmicpc.net/problem/12880

12880번: 그래프 차이 최소

선택될 수 있는 선분의 가중치 범위를 투 포인터를 이용하면서 고르고, 해당 범위에서 전체 정점이 하나의 SCC그룹으로 만들어지는지 확인하는 방법을 통해 문제를 해결했다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

int n;
int board[50][50];
vector<int> cost;

//scc
int node_id_cnt = 0;
vector<int> maked(50);
vector<int> visited(50);
vector<int> node_id(50);
deque<int> st;
int group_cnt = 0;

void Pre()
{
	for (int i = 0; i < 50; i++)
	{
		maked[i] = 0;
		visited[i] = 0;
		node_id[i] = 0;
	}

	node_id_cnt = 0;
	st.clear();
	group_cnt = 0;
}

int Dfs(int here, int min_cost, int max_cost)
{
	visited[here] = 1;
	st.push_back(here);

	node_id_cnt++;
	node_id[here] = node_id_cnt;

	int parent = node_id[here];

	for (int i = 0; i < n; i++)
	{
		int there = i;
		int there_cost = board[here][there];

		if (here == there)
			continue;

		//이동 할 수 없는 범위의 가중치일때
		if (there_cost < min_cost || there_cost > max_cost)
			continue;

		if (visited[there] == 0)
		{
			parent = min(parent, Dfs(there, min_cost, max_cost));
		}

		else if (maked[there] == 0)
		{
			parent = min(parent, node_id[there]);
		}

	}

	if (parent == node_id[here])
	{
		while (1)
		{
			int st_top = st[st.size() - 1];
			st.pop_back();

			//0에서 출발한 scc그룹에 속해있는 정점의 개수를 센다
			if (here == 0)
				group_cnt++;

			maked[st_top] = 1;

			if (st_top == here)
				break;
		}
	}

	return parent;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
			cost.push_back(input);
		}
	}

	//중복되는 값 제거
	sort(cost.begin(), cost.end());
	cost.erase(unique(cost.begin(), cost.end()), cost.end());

	//투 포인터를 이용
	int left = 0;
	int right = 0;
	int result = 987654321;
	while (1)
	{
		Pre();

		//다 확인 했을때
		if (right == cost.size() || left == cost.size())
			break;

		//cost[left] ~ cost[right] 범위의 가중치로 전체 정점을 하나의 scc그룹으로 만들 수 있는지 확인
		Dfs(0, cost[left], cost[right]);

		//cost[left] ~ cost[right] 범위 사이에서 전체 정점이 하나의 scc그룹으로 묶일때
		if (group_cnt == n)
		{
			result = min(result, cost[right] - cost[left]);
			left++;
		}

		else
		{
			right++;
		}
	}

	cout << result;

	return 0;
}