[백준 15559] 내 선물을 받아줘 (C++)

15559번: 내 선물을 받아줘

강한 연결 요소

---

임의의 칸에서 출발해서 다시 자신의 칸으로 되돌아 올 수 있으면 해당 루트의 아무 지점에 선물을 놓아도 선물을 가져갈 수 있다. 따라서 각 칸의 scc번호를 구한다.

scc번호를 구하고 scc그래프를 만드는데 역방향으로 만드는게 중요하다.

하나의 SCC집합 내부에선 어떤 칸에 놓던지 선물을 가져갈 수 있는 성질을 활용하면 된다.

SCC의 outdegree가 0이면 해당 SCC에서 다른 SCC로 갈 수 없다. (너무 당연하고)

따라서 다른 SCC에 선물이 있든 없든 outdegree가 0인 SCC에 선물이 있어야지만 선물을 얻을 수 있다.

각 SCC번호에 따른 outdegree를 구하기 위해서 그래프를 만들 때 역방향으로 만들어 주면 만들어진 그래프의 indegree가 실제 그래프의 outdegree가 되고 outdegree가 0인 SCC의 개수를 구하면 문제의 답을 구할 수 있다.

 

SCC를 사용했고 outdegree성질까지 있어서 난이도가 플레4가 적절하지않나 생각했는데 유니온파인드+dfs로 풀리는 문제였다. 어렵게 풀었지만 나름 깨달은게 있는 문제였다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M;
int Map[1001][1001];
int visited[1001][1001];
int num[1001][1001];
int outdegree[1000001];
int vcnt, ccnt;
vector<pii > stk;
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0}; // E W S N
 
void input(){
    cin >> N >> M;
    string str;
    for(int i = 0; i < N; i++){
        cin >> str;
        for(int j = 0; j < M; j++){
            switch (str[j]){
            case 'E': Map[i][j] = 0; break;
            case 'W': Map[i][j] = 1; break;
            case 'S': Map[i][j] = 2; break;
            case 'N': Map[i][j] = 3; break;
            default: break;
            }
        }
    }
    memset(visited, -1, sizeof(visited));
    memset(num, -1, sizeof(num));
}
 
int dfs(int r, int c){
    int ret = visited[r][c] = vcnt++;
    stk.push_back({r, c});
    
    int nr = r + dr[Map[r][c]];
    int nc = c + dc[Map[r][c]];
    
    if(visited[nr][nc] == -1) ret = min(ret, dfs(nr, nc));
    else if(num[nr][nc] == -1) ret = min(ret, visited[nr][nc]);
    
    if(ret == visited[r][c]){
        while(true){
            pii temp = stk.back();
            stk.pop_back();
            num[temp.first][temp.second] = ccnt;
            if(temp.first == r && temp.second == c) break;
        }
        ccnt++;
    }
    
    return ret;
}
 
void solve(){
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            if(visited[r][c] != -1) continue;
            dfs(r, c);
        }
    }
    
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            int nr = r + dr[Map[r][c]];
            int nc = c + dc[Map[r][c]];
            if(num[r][c] == num[nr][nc]) continue;
            outdegree[num[r][c]]++;
        }
    }
    int res = 0;
    for(int i = 0; i < ccnt; i++){
        if(!outdegree[i]) res++;
    }
    
    cout << res << "\n";
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}