[BOJ/백준][Gold5] 2617 : 구슬 찾기 (C++)

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

2617번: 구슬 찾기

 

 

[난이도] Gold5
[유형] DFS

[풀이]
무거운 구슬을 u, 가벼운 구슬을 v로 입력 받았을 때,
인접행렬을 이용해 adj[u][v]=1, adj[v][u]=2 와 같이 u->v 방향 edge는 1, v->u 방향 edge는 2로
표시해줍니다.

그 뒤 각 구슬에서 dfs를 1,2방향에 대해 돌려주면서 몇 개의 구슬을 방문할 수 있는지 체크해줍니다.
1 방향 edge 탐색으로 자신보다 가벼운 구슬의 개수를 찾을 수 있고,
2 방향 edge 탐색으로 자신보다 무거운 구슬의 개수를 찾을 수 있습니다.

이 두 값 중 N/2를 넘는 값이 있으면 정답에 추가해줍니다.

 

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,M,visit[100],adj[100][100],ans;
int dfs(int cur,int k){
    visit[cur]=1;
    int ret=1;
    for(int i=1;i<=N;i++){
        if(!visit[i]&&adj[cur][i]==k) ret+=dfs(i,k);
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u][v]=1;
        adj[v][u]=2;
    }
    for(int i=1;i<=N;i++){
        int v = dfs(i,1);
        memset(visit,0,sizeof(visit));
        if(v-1>N/2) {
            ans++;
        } else {
            v = dfs(i,2);
            if(v-1>N/2) ans++;
        }
        memset(visit,0,sizeof(visit));
    }
    printf("%d",ans);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2617.cpp