[Beakjoon] 2617 구슬 찾기 (C++)

문제 링크

BOJ 2617 : 구슬 찾기

문제

무게가 서로 다른 N개의 구슬이 주어진다.
N이 홀수일 때, 무게가 중간이 될 수 없는 구슬의 개수를 반환한다.

쉽게 생각하면 그래프 상에서 자식 노드의 개수가 N/2개를 넘어가는 노드의 개수를 카운트 해주는 문제이다.

풀이

이왜않의 연속이었다.

어줍잖게 효율적으로 풀겠다고 메모이제이션을 활용했다.

처음 생각은 특정 노드의 자식 개수가 이미 카운트 돼있다면, 그 값을 그대로 이용하겠다고 생각했다.

예를 들어, 2->1 순서이고, 1의 자식 개수가 3개라면
2번 노드의 자식 개수는 3+(다른 노드 계산 값)이 된다.

하지만

위와 같이 자식이 중복되는 경우 이미 저장된 값을 사용한다면 중복으로 카운트 하게 된다.
1번 노드의 자식 개수를 확인하는 과정에서, 만약 2번 노드 자식값이 이미 1로 업데이트 돼있다고 가정하자.
그럼 1번에서 계산되는 자식의 개수는 2번+3번+2번의 자식개수 1 = 3으로 계산이 되는 오류가 발생한다.

N값도 99개로 적은 값이니 그냥 정직하게 그래프 탐색을 진행하면 되는 문제이다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define endl "\n"

using namespace std;

int N, M;
bool visited[101];
vector<int> G1[101]; //무거운 구슬 -> 가벼운 구슬
vector<int> G2[101]; //가벼운 구슬 -> 무거운 구슬


int dfs1(int n){
    int next, cnt=0;

    for(int i=0; i<G1[n].size(); i++){
        next = G1[n][i];
        if(visited[next]) continue;
        visited[next] = true;

        cnt+=(dfs1(next)+1);
    }
    
    return cnt;
}

int dfs2(int n){
    int next, cnt=0;
    
    for(int i=0; i<G2[n].size(); i++){
        next = G2[n][i];
        if(visited[next]) continue;
        visited[next] = true;

        cnt+=(dfs2(next)+1);
    }

    return cnt;
}

void Solve() {
    cin>>N>>M;

    int a, b, cntH, cntL, answer=0;

    for(int i=0; i<M; i++){
        cin>>a>>b;
        G1[a].push_back(b);
        G2[b].push_back(a);
    }

    for(int i=1; i<=N; i++){
        fill(visited, visited+N+1, false);
        visited[i] = true;
        cntL = dfs1(i);
        
        
        fill(visited, visited+N+1, false);
        visited[i] = true;
        cntH = dfs2(i);
        //cout<<"i:"<<i<<"  "<<cntH<<" "<<cntL<<endl;
        if(cntH >N/2 || cntL > N/2) answer++;
    }

    cout<<answer;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();

    return 0;
}