백준 2152 - 여행 계획 세우기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2152

2152번: 여행 계획 세우기

SCC 알고리즘과 BFS, DP가 사용된 문제입니다.

S도시에서 시작해 T도시에 도착할 때, 여행할 수 있는 최대 도시 수를 구하는 문제입니다.

도시는 한번만 방문 가능한 것이 아닌 여러번 방문할수 있습니다.(여러 번 방문했다고 해도 방문한 도시의 수는 1개만 증가합니다.)

만약, ’도시들 중에 순환이 가능한 도시들이 있다면 해당 도시들을 하나의 그룹으로 생각하고 탐색을 하면 되지 않을까?‘ 라는 생각을 해보겠습니다.
예시로 다음과 같은 도시의 그래프가 주어졌다고 가정하겠습니다.

위의 도시 그래프는 서로 순환이 가능한 도시들이 생깁니다.
그렇다면 도시는 여러번 방문이 가능함으로 이런 도시들이 있다면 한번에 방문하고 다음 도시들을 탐색하러 갈 수 있을 것입니다.
따라서, 먼저 순환이 가능한 도시들을 찾아서 하나로 묶어주는 것이 필요합니다.
->SCC 알고리즘을 사용하면 됩니다.


이렇게 도시를 묶었다면, 문제에서 입력으로 주어진 도시들의 관계를 통해서 어떤 SCC가 연결이 되었는지 확인할 수 있을 것입니다.
그럼, SCC들간의 관계를 저장해, 어떤 SCC가 어떤 SCC로 연결되있는지를 찾아줍니다.

해당 관계를 통해서 시작점이 포함된 SCC애서 도착점이 포함된 SCC까지 그래프 탐색을 통해서 최대 몇개의 도시를 방문할 수 있는지 찾을 수 있습니다.

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#define F first
#define S second

using namespace std;

int N, M, S, T;
vector<vector<int>> connect;

int check[10001];
int SCC_id[10001];
vector<int> stk;
int SCC_cnt, vertex;

vector<int> SCC_step;
vector<vector<int>> SCC_connect;
vector<int> SCC_dp;
vector<int> SCC_visit;
queue<int> q;

void reset_array(){
	memset(check, -1, sizeof(check));
	memset(SCC_id, -1, sizeof(SCC_id));
}

void SCC_resize(){
	SCC_step.resize(SCC_cnt+1);
	SCC_visit.resize(SCC_cnt+1);
	SCC_dp.resize(SCC_cnt+1);
	SCC_connect.resize(SCC_cnt+1, vector<int>());
}

int SCC(int start){
	int ret = check[start] = vertex++;
	stk.push_back(start);
	for(auto &next : connect[start]){
		if(check[next] == -1){
			ret = min(ret, SCC(next));
		}
		else if(SCC_id[next] == -1){
			ret = min(ret, check[next]);
		}
	}
	if(ret == check[start]){
		while(1){
			int x = stk.back();
			stk.pop_back();
			SCC_id[x] = SCC_cnt;
			if(x == start) break;
		}
		SCC_cnt++;
	}
	return ret;
}

void bfs(){
	q.push(SCC_id[S]);
	SCC_dp[SCC_id[S]] = SCC_visit[SCC_id[S]];
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(auto &next : SCC_connect[x]){
			if(SCC_dp[next] < SCC_dp[x] + SCC_visit[next]){
				SCC_dp[next] = SCC_dp[x] + SCC_visit[next];
				q.push(next);
			}
		}
	}
}

void solve(){
	reset_array();
	for(int i = 1; i <= N; i++){ //각각의 SCC를 구한다.
		if(check[i] != -1) continue;
		SCC(i);
	}
	SCC_resize();
	for(int i = 1; i <= N; i++){ //SCC에 속해있는 도시의 수를 구한다.
		SCC_visit[SCC_id[i]]++;
		for(auto &next : connect[i]){ //각 SCC기 어떤 SCC와 연결이 되어있는지를 구한다.
			if(SCC_id[i] == SCC_id[next]) continue;
			SCC_connect[SCC_id[i]].push_back(SCC_id[next]);
			SCC_step[SCC_id[next]]++;
		}
	}
	bfs();
	cout << SCC_dp[SCC_id[T]];
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> S >> T;
	connect.resize(N+1, vector<int>());
	for(int i = 1; i <= M; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		connect[x].push_back(y);
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.