백준 2617번 구슬 찾기

문제 링크입니다: https://www.acmicpc.net/problem/2617

DFS(Depth First Search) 알고리즘을 이용해 해당 구슬보다 무겁거나 가벼운 구슬이 전체 구슬의 반 초과인지 확인하는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 해당 구슬보다 무거운 구슬과 가벼운 구슬을 입력받습니다.

2. 1~N 번째 구슬을 모두 탐색하며 해당 구슬보다 무거운 구슬과 가벼운 구슬이 몇개인지 파악합니다.

3. 2번에서 구한 두 값 중 하나라도 전체 구슬의 반 초과이면 절대 중간에 있을 수 없습니다.

#include <iostream>

#include <vector>

#include <cstring>

using namespace std;

 

const int MAX = 100;

 

int N, M;

vector<int> heavier[MAX], lighter[MAX];

bool hVisited[MAX], lVisited[MAX];

 

int HDFS(int node)

{

        int result = 1;

        for (int i = 0; i < heavier[node].size(); i++)

        {

                 if (!hVisited[heavier[node][i]])

                 {

                         hVisited[heavier[node][i]] = true;

                         result += HDFS(heavier[node][i]);

                 }

        }

        return result;

}

 

int LDFS(int node)

{

        int result = 1;

        for (int i = 0; i < lighter[node].size(); i++)

        {

                 if (!lVisited[lighter[node][i]])

                 {

                         lVisited[lighter[node][i]] = true;

                         result += LDFS(lighter[node][i]);

                 }

        }

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

        for (int i = 0; i < M; i++)

        {

                 int marble1, marble2;

                 cin >> marble1 >> marble2;

 

                 heavier[marble1].push_back(marble2);

                 lighter[marble2].push_back(marble1);

        }

 

        vector<bool> result(N + 1);

        for (int i = 1; i <= N; i++)

        {

                 memset(hVisited, false, sizeof(hVisited));

                 memset(lVisited, false, sizeof(lVisited));

                 hVisited[i] = true, lVisited[i] = true;

 

                 //중간이 될 수 없는 조건

                 if (HDFS(i) > (N + 1) / 2)

                         result[i] = true;

                 if (LDFS(i) > (N + 1) / 2)

                         result[i] = true;

        }

 

        int cnt = 0;

        for (int i = 0; i < N + 1; i++)

                 if (result[i])

                         cnt++;

 

        cout << cnt << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~