[ BOJ 백준 4196번 - 도미노 ] 해설 및 코드

 

 

목적

배치되어 있는 도미노 블록간의 관계가 주어질 때, 모든 블록을 넘어뜨리기 위해 최소 몇 개의 블록을 넘어뜨려야 하는지 구하자.

 

접근법

1. 결론부터 말하면, 위상정렬을 해준 후에 dfs를 수행하면 된다. (dfs 두번..)

 

2. 위상 정렬은 사이클이 없는 방향그래프(DAG)에 적용될 수 있지만, 사이클을 형성하는 정점들 간의 위상은 고려하지 말자. 위상 정렬을 한 뒤에는 시작 정점에서 끝 정점 순으로 정렬이 될테니, 정렬된 순으로 dfs 탐색으로 이어지는 다음 정점들을 제거하면서 그래프의 시작 정점들을 카운트 해준다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
const int MAXN=1e5+1;
vector<vector<int>> edge;
bool vis[MAXN];
int p[MAXN], idx;
 
void sort(int u){
    vis[u]=true;
    for(int v:edge[u])if(!vis[v])sort(v);
    p[idx--]=u;
}
void dfs(int u){
    vis[u]=true;
    for(int v:edge[u])if(!vis[v])dfs(v);
}
 
int sol(){
    int n,m;cin>>n>>m;
    edge.resize(n+1);
    while(m--){
        int a,b;cin>>a>>b;
        edge[a].push_back(b);
    }
    
    memset(vis, false, n+1);
    idx=n;
    f(i,1,n)if(!vis[i])sort(i);
    
    int cnt=0;
    memset(vis, false, n+1);
    f(i,1,n)if(!vis[p[i]]){
        ++cnt;
        dfs(p[i]);
    }
    edge.clear();
    return cnt;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;cin>>t;
    while(t--)cout<<sol()<<'\n';
    return 0;
}
 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.