2617번 구슬 찾기

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

쉬운 DFS 유형 문제이다.

예제 1을 방향 그래프 2개(무거운지, 가벼운지)를 그려서, 생각해보니 구현 방법이 떠올랐다.

사실상 같은 정답 코드 2개를 첨부한다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
vector<int> h[100], l[100];
 
int N = 0, M = 0;
 
bool visit[100] = { false, };
 
int cnt = 0;
 
void lDFS(int start)
{
    visit[start] = true;
 
    for (auto i : l[start])
    {
        if (!visit[i])
        {
            ++cnt;
 
            lDFS(i);
        }
    }
}
 
void hDFS(int start)
{
    visit[start] = true;
 
    for (auto i : h[start])
    {
        if (!visit[i])
        {
            ++cnt;
 
            hDFS(i);
        }
    }
}
 
int main(void)
{
    int s = 0, e = 0, result = 0;
 
    scanf("%d %d", &N, &M);
 
    while (M--)
    {
        scanf("%d %d", &s, &e);
 
        l[s].push_back(e); // s보다 가벼운 것들을 push_back
        h[e].push_back(s); // e보다 무거운 것들을 push_back
    }
 
    for (int i = 1; i <= N; i++)
    {
        memset(visit, false, sizeof(visit));
        cnt = 0;
 
        hDFS(i);
 
        if (cnt >= (N + 1) / 2)
        {
            ++result;
            continue;
        }
 
        memset(visit, false, sizeof(visit));
        cnt = 0;
 
        lDFS(i);
 
        if (cnt >= (N + 1) / 2) ++result;
    }
 
    printf("%d\n", result);
 
    return 0;
}

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
vector<int> h[100], l[100];
 
int N = 0, M = 0;
 
bool visit[100] = { false, };
 
int lDFS(int start)
{
    visit[start] = true;
 
    int ret = 0;
 
    for (auto i : l[start]) if (!visit[i]) ++ret += lDFS(i);
    
    return ret;
}
 
int hDFS(int start)
{
    visit[start] = true;
 
    int ret = 0;
 
    for (auto i : h[start]) if (!visit[i]) ++ret += hDFS(i);
    
    return ret;
}
 
int main(void)
{
    int s = 0, e = 0, result = 0;
 
    scanf("%d %d", &N, &M);
 
    while (M--)
    {
        scanf("%d %d", &s, &e);
 
        l[s].push_back(e);
        h[e].push_back(s);
    }
 
    for (int i = 1; i <= N; i++)
    {
        memset(visit, false, sizeof(visit));
 
        if (hDFS(i) >= (N + 1) / 2)
        {
            ++result;
            continue; // 어차피 여기서 조건에 맞다면, 아래는 안 봐도 된다.
        }
 
        memset(visit, false, sizeof(visit));
 
        if (lDFS(i) >= (N + 1) / 2) ++result;
    }
 
    printf("%d\n", result);
 
    return 0;
}