[백준 C++] 4013 ATM

문제

인도의 도시 중 하나인 시루세리에는 모든 도로들이 일방통행으로 되어 있다. 도로들이 만나는 모든 교차로에는 시루세리 은행의 현금입출금기(ATM)가 설치되어 있다. 시루세리에는 유명한 레스토랑 체인인 아웃백 커리 하우스가 있다. 이 레스토랑의 각 체인점들은 교차로에만 위치한다. 물론 각 교차로마다 항상 이 레스토랑 체인점이 있는 것은 아니다. 이 레스토랑은 현금만 사용할 수 있다.

시루세리에 사는 반디치는 오늘 오후에 이 레스토랑에서 가족들과 파티를 열려고 한다. 그런데 갖고 있는 현금이 부족하여 레스토랑으로 가는 동안에 가능한 한 많은 현금을 ATM 기기로부터 인출할 계획을 세웠다. 그는 자신의 집에서 출발하여 차로 이동하면서 통과하는 모든 교차로 ATM 기기에 들어있는 현금 전부를 인출하려고 한다. 차량의 최종 목적지는 아웃백 커리 하우스 체인점 중의 한 곳이고, 이 체인점이 어떤 교차로에 위치하는지는 상관없다.

반디치는 시루세리 은행의 홈페이지 정보를 통해 각 ATM 기기에 현금이 얼마나 들어 있는지를 알고 있다. 이동 시 동일한 도로나 교차로를 여러 번 지날 수 있다. ATM 기기의 현금은 새로 보충되지 않기 때문에 첫 번째 이후 다시 방문하는 교차로의 ATM 기기에는 인출할 현금이 없다.

예를 들어, 아래 그림처럼 도시에 6개의 교차로가 있다고 하자. 교차로는 원으로 표시되어 있고, 화살표는 도로를 나타낸다. 이중 원으로 표시된 교차로에는 레스토랑이 있다. 각 ATM 기기가 갖고 있는 현금의 액수는 교차로 위에 표시된 숫자이다. 이 예에서 현금 인출을 1번 교차로부터 시작한다면, 반디치는 1-2-4-1-2-3-5의 경로를 통해서 총 47의 현금을 인출할 수 있다.

반디치가 출발 장소에서 어떤 레스토랑까지 이동하면서 인출할 수 있는 현금의 최대 액수가 얼마인지를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차로 번호와 끝 교차로 번호를 나타내는 2개의 정수가 주어진다. 그 다음 N개의 줄에는 1번 교차로부터 차례대로 각 교차로의 ATM 기기가 보유한 현금의 액수를 나타내는 정수가 각 줄에 하나씩 주어진다. 그 다음 줄에는 두 개의 정수 S와 P가 주어진다. 여기서 S는 출발 장소(현금 인출의 시작 장소)인 교차로 번호이고 P는 레스토랑의 개수이다(1 ≤ P ≤ N). 그 다음 줄에는 각 레스토랑이 있는 교차로의 번호를 나열한 P개의 정수가 주어진다.

각 ATM 기기에 들어 있는 현금의 액수는 0 이상 4,000 이하이다. 모든 입력에서 경로의 출발 장소로부터 일방통행 도로를 통해 도달 가능한 레스토랑이 항상 하나 이상 존재한다.

출력

출력은 한 개의 정수이다. 이 정수는 반디치가 출발 장소에서 어떤 레스토랑까지 이동하면서 인출할 수 있는 현금의 최대 액수이다.

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

풀이

SCC를 만든뒤에 만들어진SCC에 레스토랑의 존재여부, SCC내 모든 현금총합을 가지고
BFS탐색을해서 최댓값을 찾도록 요구하는 문제이다.
왜이렇게 되냐하믄
먼저 정점과 간선은 여러번 지날수 있고, 정점을 지날때 한번만 현금을 가진다. 그리고 최종목적지는 레스토랑이 존재하는 정점일때 그래프에서 수집 가능한 최댓값을 찾아달란것이 문제다.
여기서 정점과 간선을 여러번 지날수 있으니 사이클이 존재하면 하나로 묶어서 생각가능하기에 SCC로 묶어야한다.
그리고 SCC마다 레스토랑존재여부를 기록하여
최종목적지가 레스토랑이 존재하는 SCC일때만 출력값 res의 최댓값을 갱신하면되는것.
즉 만들어진 SCC를 하나의 정점으로보아
BFS를 새로 진행하라 이말이다.

1. SCC를 만들기위한 DFS코드
   특이한점이면 이번엔 visited배열대신 스택에서 POP을 할때 각 정점이 몇번 SCC에 속하는지 기록하는 group배열을 사용한다는것.
   또, 위에서 설명하듯 SCC에 레스토랑이존재하는지, 또 시작정점을 포함하는 SCC면 시작 SCC그룹번호를 설정해주었다.
   
   
   
2. 최종적으로 SCC를 완성시키고, 각 SCC를 하나의 정점으로 보아 서로 연결됨을 SCCedge에 기록하는 코드
   서로 연결이있는 x -> y인 두 정점이
   서로 다른 SCC에 속하면
   SCC[group[x]] -> SCC[group[y]] 임을 SCCedge에 기록한다. 이걸 이용해 BFS를 돌릴것이다.
   
   
   
3. SCC를 하나의 정점으로 보며 BFS를 진행해 최댓값을 찾는 코드
   SCCmoneySumMAX의 최댓값이 갱신될때마다 큐에 넣으며,
   큐에서 꺼낼때 레스토랑이 존재하는 SCC그룹이라면 res의 최댓값을 갱신한다.
   최종적인 출력은 res가 된다.
   여기서 SCCmoneySumMAX배열없이 큐에 바로바로 값을 전달하면
   메모리 초과가 나더라.. 어떻게 최적화 할지 찾다가 포기..

결국 SCC를 만든뒤 위상정렬하는 문제로 구현양이 상당해서 플레2문제인듯하다.. 끔찍했다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
#define mp std::make_pair 
#define mt std::make_tuple
#define dq std::deque
#define pq std::priority_queue
#define sw std::swap
#define ts(x) std::to_string(x)
#define tc() c_str()
#define sc(x, ...) scanf(x, ##__VA_ARGS__) 
#define pr(x, ...) printf(x, ##__VA_ARGS__) 
#define ins(x) insert(x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define PB() pop_back()
#define PF() pop_front()
#define ph(x) push(x)
#define TT() top()
#define PP() pop()
#define BB() back()
#define FF() front()
#define cls() clear()
#define emp() empty()
#define len(x) x.length()
#define sz(x) ((int)x.size()) //컨테이너에서 사용
#define ms(a) memset(a, 0, sizeof(a)) //0으로 초기화
#define rep(i, n) for(int i = 0; i < n ; i++)
#define rrep(i, r, n) for(int i = r; i < n ; i++)
#define rrrep(i, r, n) for(ll i = r; i < n ; i++)
#define _rrep(i, r, n) for(int i = r; i >= n; i--)
#define _rrrep(i, r, n) for(ll i = r; i >= n; i--)
#define each(x, a) for (auto& x: a)
#define all(x) x.begin(),x.end() //STL에서 전체 처리할때 사용
#define range(x, r, n) x.begin() + r, x.begin() + n //STL에서 구간설정
#define ct continue
#define br break
#define rt return
#define _TYF typedef //코드줄이기
#define _UG using
#define _TCE template <class T> inline
#define MAX 500001 
const int IMAX = INT32_MAX; const int IMIN = INT32_MIN;
const long long LMAX = LLONG_MAX; const long long LMIN = LLONG_MIN;
const long double PI = 3.141592653589793238462643383279502884197;
_UG std::vector; _UG std::stack; _UG std::queue; _UG std::tuple; _UG std::set; _UG std::list; _UG std::bitset; _UG std::string; _UG std::pair; _UG std::greater;
_UG std::tie; _UG std::sort; _UG std::max_element; _UG std::min_element; _UG std::fill; _UG std::stoi; _UG std::stod; _UG std::stof; _UG std::stol; _UG std::stold; _UG std::stoll; _UG std::stoul; _UG std::stoull;
_UG std::min; _UG std::max;
_TYF long long ll; _TYF unsigned long long ull;
_TYF pair<int, int> pii; _TYF pair<double, int> pdi; _TYF pair<int, double> pid; _TYF pair<double, double> pdd; _TYF pair<int, ll> pil;
_TYF pair<ll, int> pli; _TYF pair<ll, ll> pll; _TYF pair<ull, ull> pullull; _TYF pair<int, char> pic; _TYF pair<char, int> pci;
_TYF pair<char, char> pcc; _TYF pair<long, char> plc; _TYF pair<char, long> pcl; _TYF pair<ll, char> pllc; _TYF pair<char, ll> pcll;
_TYF pair<ull, char> pullc; _TYF pair<char, ull> pcull; _TYF pair<int, string> pis; _TYF pair<string, int> psi; _TYF pair<long, string> pls;
_TYF pair<string, long> psl; _TYF pair<ll, string> plls; _TYF pair<string, ll> psll; _TYF pair<ull, string> pulls;
_TYF pair<string, ull> psull; _TYF pair<string, string> pss;
_TYF tuple<int, int, int> tiii; _TYF tuple<int, int, int, int> tiiii;
_TYF tuple<ll, ll, ll> tlll; _TYF tuple<ll, ll, ll, ll> tllll;
_TYF vector<string> vs; _TYF queue<string> qs; _TYF stack<string> ss; _TYF dq<string> dqs; _TYF pq<string> pqs; _TYF dq<string> dqs;
_TYF vector<char> vc; _TYF queue<char> qc; _TYF stack<char> sc; _TYF dq<char> dqc; _TYF pq<char> pqc; _TYF dq<char> dqc;
_TYF vector<int> vi; _TYF queue<int> qi; _TYF stack<int> si; _TYF dq<int> dqi; _TYF pq<int> pqi; _TYF dq<int> dqi;
_TYF vector<pii> vii; _TYF queue<pii> qii; _TYF stack<pii> sii; _TYF dq<pii> dqii; _TYF pq<pii> pqii; _TYF dq<pii> dqii;
_TYF vector<tiii> viii; _TYF queue<tiii> qiii; _TYF stack<tiii> siii; _TYF dq<tiii> dqiii; _TYF pq<tiii> pqiii; _TYF dq<tiii> dqiii;
_TYF vector<tiiii> viiii; _TYF queue<tiiii> qiiii; _TYF stack<tiiii> siiii; _TYF dq<tiiii> dqiiii; _TYF pq<tiiii> pqiiii; _TYF dq<tiiii> dqiiii;
_TYF vector<pll> vll; _TYF queue<pll> qll; _TYF stack<ll> sll; _TYF dq<pll> dqll; _TYF pq<pll> pqll; _TYF dq<pll> dqll;
_TYF vector<tlll> vlll; _TYF queue<tlll> qlll; _TYF stack<tlll> slll; _TYF dq<tlll> dqlll; _TYF pq<tlll> pqlll; _TYF dq<tlll> dqlll;
_TYF vector<tllll> vllll; _TYF queue<tllll> qllll; _TYF stack<tllll> sllll; _TYF dq<tllll> dqllll; _TYF pq<tllll> pqllll; _TYF dq<tllll> dqllll;
_TCE T sq(T num) { rt num* num; }//제곱함수
_TCE T GCD(T num1, T num2) { if (num2 == 0) rt num1; rt GCD(num2, num1 % num2); }
_TCE T LCM(T num1, T num2) { if (num1 == 0 || num2 == 0) rt num1 + num2; rt num1* (num2 / GCD(num1, num2)); }
//STL 전용 초기화 함수들 ( ms~~ )
_TCE void msq(T& a) { while (!a.empty()) a.PP(); }//queue clear
_TCE void msv(T& a) { a.cls(); }//vector clear
_TCE void msdq(T& a) { a.cls(); }//deque clear
_TCE void msm(T& a) { a.cls(); }//map clear
_TCE void mss(T& a) { while (!a.empty()) a.PP(); }//stack, set clear
_TCE void mspq(T& a) { while (!a.empty()) a.PP(); }//priority_queue clear
//pii operator - (pii a, pii b) { rt pii(a.first - b.first, a.second - b.second); }
//bool operator <= (pii a, pii b) { rt a.first <= b.first && a.second <= b.second; } 
//bool operator >= (pii a, pii b) { rt a.first >= b.first && a.second >= b.second; } 
//bool operator < (pii a, pii b) { if (a == b) return false; rt a <= b; } 
//bool operator > (pii a, pii b) { if (a == b) return false; rt a >= b; }

//////////////입력, DFS에서 사용될 요소/////////////////////
int N, M; //정점갯수, 간선갯수
vi road[MAX]; //교차로간의 연결된 다른 교차로를 기록 (단방향 간선)
int money[MAX]; //정점(교차로)의 ATM기가 갖는 현금
int S, P; //출발위치 정점번호, 레스토랑 총갯수 P
int idx, p[MAX]; //정점에매겨질 번호, 정점마다 자신의 부모를 저장하는 배열
si s; //DFS에서 SCC만듦에 사용될 스택
////////////////////////////////////////////////////////////
/////////////SCC그룹마다에 사용될 요소//////////////////////
int SCCcnt = 1; //SCC그룹에 매겨질 번호. 1부터 시작한다.
bool restaurant[MAX]; //정점(교차로)에 레스토랑이 있는가 <= 입력받는 값
int group[MAX]; //정점(교차로)이 어느 SCC그룹에 속하는가 SCCcnt값으로.
int SCCmoney[MAX]; //SCC그룹마다 내부 정점들이 가진 현금총합
bool SCChasRestaurant[MAX]; //SCC그룹이 레스토랑을 포함하고있는가
int SCCstartNum; //SCC그룹중 현금합계를 시작할 번호
vector<int> SCCedge[MAX];  //SCC에서 연결된. 다음으로 이동가능한 다음SCC번호를 저장 <= BFS에서 사용
int SCCmoneySumMAX[MAX]; //해당하는 SCC그룹도착지라 칠때 거쳐온 모든경로들간의 현금총합 중 최댓값을 저장 <= BFS로 갱신해나갈것
int res; //출력할 값 (최댓값)
////////////////////////////////////////////////////////////
void init();
int DFS(int x);
void bfs();
void func();

void init() {
	sc("%d%d", &N, &M);
	rep(_, M) { //도로 상황 
		int s, e;
		sc("%d%d", &s, &e);
		road[s].pb(e);
	}
	rrep(i, 1, N+1) { //각 교차로의 ATM이 가지는 금액
		int m;
		sc("%d", &m);
		money[i] = m;
	}
	sc("%d%d", &S, &P); //시작위치, 레스토랑 총갯수 
	rep(_, P) {
		int r;
		sc("%d", &r);
		restaurant[r] = true;
	}
}

int DFS(int x) {
	p[x] = ++idx;
	s.ph(x);

	int parent = p[x];
	rep(i, sz(road[x])) {
		int y = road[x][i];
		if (p[y] == 0) //아직 탐색하지 않은 정점이 있으면
			parent = min(parent, DFS(y));
		else if (!group[y]) //탐색은 했으나 SCC그룹에 속하지 않은 정점이있으면(사이클도는중)
			parent = min(parent, p[y]);
	}

	if (parent == p[x]) {
		while (x) {
			int y = s.TT();
			s.PP();
			group[y] = SCCcnt; //현재 정점에대해 SCC그룹번호를 매긴다. (1부터 매겨짐)
			SCCmoney[SCCcnt] += money[y]; //SCC그룹내의 현금 총합 갱신
			if (restaurant[y]) //현재 정점에 레스토랑이 존재하면
				SCChasRestaurant[SCCcnt] = true;  //속하는 SCC그룹에 레스토랑이 존재한다고 표기함
			if (S == y) //현재 정점이 시작정점이면
				SCCstartNum = SCCcnt; //속하는 SCC그룹으로부터 BFS탐색을 시작해줘용 ~

			if (y == x) br;
		}
		SCCcnt++;
	}

	rt parent;
}


void bfs() {
	qi q;
	q.ph(SCCstartNum); //SCCstartNum : DFS에서구한 시작할 SCC그룹번호
	SCCmoneySumMAX[SCCstartNum] = SCCmoney[SCCstartNum]; //해당하는 SCC그룹이
	while (!q.emp()) {
		int sccCurNum = q.FF();
		q.PP();
		//현재 SCC번호에 레스토랑이 존재하면 최댓값을갱신함
		if (SCChasRestaurant[sccCurNum])
			res = max(res, SCCmoneySumMAX[sccCurNum]);
		//현재 SCC그룹에 속하는 구성원(각 정점들)을 다음 정점으로하여
		//다음 정점인 sccNextNum이 속하는 다른 SCC그룹의 현금총합이 최댓값으로 갱신될 수 있는지 확인
		//무조건 sccCurNum이 속하는 SCC그룹과 sccNextNum이 속하는 SCC그룹은 다르다.!!! <= func()에서정의했기때문
		//SCCmoneySumMAX : SCC그룹내의 현금총합
		rep(i, sz(SCCedge[sccCurNum])) {
			int sccNextNum = SCCedge[sccCurNum][i];
			//최댓값이 갱신될때만 SCCmoneySumMAX를 갱신
			if (SCCmoneySumMAX[sccNextNum] < SCCmoneySumMAX[sccCurNum] + SCCmoney[sccNextNum]) {
				SCCmoneySumMAX[sccNextNum] = SCCmoneySumMAX[sccCurNum] + SCCmoney[sccNextNum];
				//갱신한다면 최댓값이 가능한루트이므로 다음에 탐색할 요소로 간주하여 큐에 넣습니다.
				q.ph(sccNextNum);
			}
		}
	}
}


//프로그램 메인 로직
void func() {
	//DFS를 이용해 SCC를 만드는 알고리즘
	rrep(i, 1, N + 1) 
		if (p[i] == 0) DFS(i); 

	//서로다른 SCC간에 단방향그래프(사이클이없는)를 SCCedge을 통해 구현
	rrep(x, 1, N + 1) {
		rep(i, sz(road[x])) {
			int y = road[x][i];
			//서로 연결된 두정점 x, y가 x - > y 일때
			//두 정점이 서로다른 SCC에 속한경우
			//x가속하는 SCC그룹이 y가속하는 SCC그룹으로의 연결을 가짐을 저장한다.
			if (group[x] != group[y]) 
				SCCedge[group[x]].pb(group[y]);
		}
	}

	//저장된 SCCedge을 이용해 BFS를 진행한다.
	bfs();
	pr("%d", res);
}

int main(void) {
	init();
	func();

	rt 0;
}