[백준] 2617 구슬 찾기 DFS

문제 :

www.acmicpc.net/problem/2617

2617번: 구슬 찾기

 

분석 :

이 문제는 배열을 두개로 나눠서 쓸 생각을 못해서 배열을 어떻게 담아야 하는지 타입에 관해 고민이 많았다. 심지어 내가 잘 못쓰는 재귀함수까지 사용해서 감 잡기가 어려웠다 😅

문제에서 원하는 것은 무게가 중간이 될 수 없는 구슬의 수를 찾으라고 한다.

중간이 될 수 없으려면 각각 담은 light, heavy vector에 인접한 노드들이 많이 담겨 비교가 많이 되어야 한다. 

따라서 dfs 를 돌때마다 lank 값이 증가하고 중간 이상의 값을 가진 노드에 대해 check 함수를 통해 저장해 놓는다. 

문제의 뜻을 파악했다면 전형적인 dfs 문제로 보일 듯 하다. 

 

 

c++ 코드 :

//
//  2617_ㅡmarble.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/11.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stack>

using namespace std;

#define MAX 101
int n, N;
bool visit[2][MAX];
vector<int> light[MAX];
vector<int> heavy[MAX];
bool check[MAX];
int cnt = 0;

int find_marble_dfs(int start, vector<int> graph[MAX], int row){//row 로 graph == heavy, light 인지 판별
    int Lank = 1; // 현재 순위
    for(int i = 0; i < (int)graph[start].size(); i++){
        if(visit[row][graph[start][i]] == false){
            visit[row][graph[start][i]] = true; // dfs 돌 수록 비교할 구슬이 많다는 것 따라서 순위 크기가 증가 (ex> 1 -> 8)
            Lank += find_marble_dfs(graph[start][i], graph, row);
        }
    }
    return Lank;
}


int main(){
    int n, N;
    cin >> n >> N;

    for(int i = 0; i< N; i++){
        int m1, m2; //m1 > m2
        cin >> m1 >> m2;
        light[m1].push_back(m2);
        heavy[m2].push_back(m1);
    }

    for (int i = 1; i <= n; i++) { // n = 구슬 번호 1 ~ n
        memset(visit, false, sizeof(visit));
        visit[0][i] = visit[1][i] = true;

        int h_rank = find_marble_dfs(i, heavy, 0);
        int l_Lank = find_marble_dfs(i, light, 1);

        if (h_rank > (n + 1) / 2 || l_Lank > (n + 1) / 2){ // 중간이 아닌 구슬들 check
            check[i] = true;
        }
    }

    for (int i = 0; i <= n; i++){
        if (check[i] == true){
            cnt++; //
        }
    }

    cout << cnt << endl;
        return 0;
}