백준 9666번 SUMO

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

이분 그래프(Bipartite graph)와 이분탐색을 이용하여 푸는 문제였습니다.

문제에서 요구하는 바는 제일 효율적으로 팀을 나누었을 때 첫 번째로 같은 팀 출신의 선수가 마주치는 싸움의 순서를 구하는 것입니다. 

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

1. 선수들이 입력될 때 양방향 그래프로 입력을 받고 몇 번째 싸움인지도 저장합니다.

2. 이분 탐색을 진행해서 해당 싸움이 같은 팀끼리 싸우는지 혹은 다른 팀끼리 싸우는지를 확인합니다.

-> 몇 번째 싸움인지 저장하는 이유가 여기서 나옵니다. 이분 탐색을 할 때 해당 싸움 이후로는 확인할 필요가 없습니다.

3. 이분 탐색이 끝나고 나면 low에 제일 처음으로 같은 팀끼리 싸운 경기의 순서가 저장되어있으므로 low를 출력합니다.

이분 그래프가 생소하신 분들은 백준 1707번 이분 그래프(http://jaimemin.tistory.com/648)를 참고하시면 됩니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 100000 + 1;

 

int N, M;

int limit;

int color[MAX];

vector<pair<int, int>> graph[MAX];

bool biPartial;

 

void DFS(int num, int c)

{

        if (color[num])

        {

                 //이분 그래프가 아닐 경우

                 if(color[num] != c)

                         biPartial = false;

                 return;

        }

 

        color[num] = c;

        for (int i = 0; i < graph[num].size(); i++)

        {

                 int next = graph[num][i].first;

                 int nextIdx = graph[num][i].second;

                 //nextIdx부터는 볼 필요 없다

                 if (nextIdx >= limit)

                         continue;

 

                 DFS(next, !c);

        }

}

 

//이분 그래프인가?

bool isBiPartite(int idx)

{

        memset(color, 0, sizeof(color));

        limit = idx;

        biPartial = true;

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

                 //색깔 0인 그룹 확인

                 if (color[i] == 0)

                         DFS(i, 0);

 

        return biPartial;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

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

        {

                 int num1, num2;

                 cin >> num1 >> num2;

 

                 //양방향

                 graph[num1].push_back({ num2, i });

                 graph[num2].push_back({ num1, i });

        }

 

        int low = 1, high = M;

        while (low <= high)

        {

                 int mid = (high + low) / 2;

 

                 if (isBiPartite(mid))

                         low = mid + 1;

                 else

                         high = mid - 1;

        }

        cout << low << "\n";

        return 0;

}

개발환경:Visual Studio 2017

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