[백준] 4013번 ATM

4013 ATM

문제)

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

풀이)

SCC, dp를 이용해서 푸는 어려웠던 문제였다.

같은 간선을 여러번 사용할 수 있기 때문에,

임의의 정점을 방문한다고 할때 그 정점이 속한 SCC내의 모든 정점을 방문해서 최대 현금을 구한다.

과정

1. kosaraju algorithm을 이용해 SCC을 구한다.

   SCC를 구할때, 각 정점이 어떤 SCC에 속하는지 표시해준다 //int node[i] => i 번 정점이 속하는 SCC번호

                      각 정점이 속하는 SCC의 총 현금을 저장해준다 //int scc[i] => i 번 SCC의 총 현금, 즉 SCC에 속한 정점들의 현금 합

     SCC 끼리 연결될 수 있다면, 그 연결 간선을 저장해준다 //vector<int> adj_scc[i] => i번 SCC와 연결되있는 다른 SCC 번호 저장

2. 레스토랑이 속한 SCC를 체크한다. // bool rest[i] == true => i번 SCC 내에는 레스토랑이 존재

3. SCC끼리의 연결 정보를 1번 과정에서 미리 저장했으므로, 그 정보를 이용해

   출발 정점 SCC에서 각 레스토랑 정점이 속한 SCC까지 BFS로 탐색한다.

   (탐색하면서, 레스토랑이 속한 SCC에 도달할 때 얻을 수 현금값을 배열에 memoization해준다.)

   //int dp[i] = 출발지 SCC에서 레스토랑이 속한 i번 SCC까지 도달하는 데 얻을 수 있는 최대 현금값

4. dp[i] 중 최대값을 출력한다.

요약 ∴ SCC를 이용한 DAG를 만들고, 그 그래프을 BFS로 탐색하며 DP로 현금 합 최대를 찾는다.

설명하기 어렵다.. 중간중간 사용하는 변수명들이 많아 햇갈릴 수 있으니

코드를 한줄씩 읽어보는 게 도움이 될 것이다.

코드)

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
 
int N, M, x, y, s, p;
int cash[500001]; //각 정점의 돈
bool visited[500001];
bool rest[500001]; //scc안에 레스토랑 정점이 속해있는지 확인
vector<int> adj[500001];
vector<int> adj2[500001];
vector <int> adj_scc[500001]; //각 scc끼리 연결간선 저장
stack<int> st;
int scc[500001];//각 scc에 속하는 정점들의 현금 합
int node[500001];//각 정점이 어떤 scc에 속하는지
int scc_num = 1;
int dp[500001];
 
void dfs(int v) {
    visited[v] = true;
    for (int i = 0; i < adj[v].size(); i++) {
        if (visited[adj[v][i]])continue;
        dfs(adj[v][i]);
    }
    st.push(v);
}
void dfs2(int v, int num) {
    visited[v] = true;
    scc[num] += cash[v];
    node[v] = num;
    for (int i = 0; i < adj2[v].size(); i++) {
        int next = adj2[v][i];
        if (visited[next]) { //이미 방문한 정점
            if (node[next] != node[v]) {//방문했던 정점이 다른 scc에 속하는 정점이면
                adj_scc[node[next]].push_back(node[v]);//scc끼리 연결
            }
    
        }
        else {
            dfs2(next, num);
        }
    }
}
int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj2[y].push_back(x);
    }
    for (int i = 1; i <= N; i++) {
        scanf("%d", &cash[i]);
    }
    scanf("%d %d", &s, &p);
    
    //과정 1
    //kosaraju algorithm : scc 만듬
    for (int i = 1; i <= N; i++) {
        if (visited[i]) continue;
        dfs(i);
    }
    memset(visited, false, sizeof(visited));
    while (!st.empty())
    {
        int here = st.top();
        st.pop();
        if (visited[here])continue;
        dfs2(here, scc_num++);
 
    }
    //과정 2
    //레스토랑 정점이 속한 scc 표시
    for (int i = 1; i <= p; i++) {
        int temp;//레스토랑 정점번호
        scanf("%d", &temp);
        rest[node[temp]] = true;
    }
    //과정 3
    //출발지 scc부터 scc들 사이 이동하며, 도달 가능한 레스토랑scc까지 최고 현금값 구함, dp + bfs
    queue<int> qu;
    qu.push(node[s]);//출발지 scc부터
    dp[node[s]] = scc[node[s]];
    int result = 0;
    while (!qu.empty())
    {
        int here = qu.front();//scc번호
        qu.pop();
        if (rest[here]) {//레스토랑이 속한 scc 였다면
            result = result < dp[here] ? dp[here] : result;
        }
        for (int i = 0; i < adj_scc[here].size(); i++) {
            int next = adj_scc[here][i];//연결된 다른 scc
            if (dp[next] < dp[here] + scc[next]) {
                dp[next] = dp[here] + scc[next];
                qu.push(next);
            }
        }
    }
    printf("%d\n", result);
    return 0;
}