백준 11977번 Angry Cows(Bronze)

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

모든 소를 터뜨려보면서 최대 연쇄횟수가 몇 번인지를 확인하면 되는 문제였습니다.

#include <iostream>

#include <queue>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 100;

 

int N, result;

int hay[MAX];

bool visited[MAX];

 

void explode(int index)

{

        queue<pair<int, int>> q; //idx, range

        q.push({ index, 1 });

        visited[index] = true;

 

        while (!q.empty())

        {

                 int idx = q.front().first;

                 int range = q.front().second;

                 q.pop();

 

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

                         //조건 성립시 큐에 넣는다

                         if (i != idx && !visited[i] && abs(hay[i] - hay[idx]) <= range)

                         {

                                 visited[i] = true;

                                 q.push({ i, range + 1 });

                         }

        }

 

        int cnt = 0;

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

                 if (visited[i])

                         cnt++;

 

        result = max(result, cnt);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

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

                 cin >> hay[i];

 

        //정렬

        sort(hay, hay + N);

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

        {

                 memset(visited, false, sizeof(visited));

                 explode(i);

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

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