문제
사자와 토끼는 전국적으로 인기를 끌고 있는 재밌는 보드게임이다. 사자와 토끼를 즐기기 위해서는 2명의 플레이어와 1명의 심판이 필요하다. 보드판은 N개의 수풀과 M개의 오솔길로 이루어져 있다. 오솔길은 서로 다른 두 수풀을 양방향으로 연결하며, 어떤 수풀에서 다른 수풀까지 1개 이상의 오솔길을 통하면 반드시 도달 할 수 있다.
게임은 다음과 같은 순서로 이루어진다.
-
심판이 사자와 토끼의 초기 위치를 각각 어느 수풀로 할지 정한다. 사자와 토끼의 초기 위치는 같을 수 없으며, 사자의 위치는 사자 플레이어에게만, 토끼의 위치는 토끼 플레이어에게만 알려준다.
-
매 턴마다, 사자와 토끼는 현재 위치한 수풀에서 오솔길 1개를 따라 이동해야 한다. 두 플레이어는 자신의 말을 이동할 위치를 심판에게만 말한다. 이동하지 않을 수는 없다.
-
이동한 후, 사자와 토끼가 같은 수풀에 있다면 사자가 토끼를 잡아먹어 게임이 끝난다. 그렇지 않다면, 다시 2로 돌아가 턴을 계속하여 진행한다. 물론 게임이 끝나지 않는 이상, 이동 후에도 두 플레이어는 상대 말의 위치를 알 수 없다. 또한, 사자는 오솔길 위에서는 토끼를 볼 수 없기 때문에, 같은 오솔길을 통해 이동하여도 서로 다른 수풀에 도착했다면 게임이 끝나지 않는다.
이렇게 서로 심리전을 통해 토끼는 사자에게서 도망가고, 사자는 토끼를 찾아내는 게임이다. 그런데 보드의 모양과 사자와 토끼의 초기 위치에 따라서, 어떻게 움직여도 영원히 게임이 끝나지 않는 경우가 있다는 것을 발견했다. 예를 들어, 위의 그림과 같은 보드판에서는 게임이 끝나지 않는 (사자의 초기 위치, 토끼의 초기 위치)의 조합은 다음과 같이 8가지가 존재한다 : (1,2) (1,4) (2,1) (2,3) (3,2) (3,4) (4,1) (4,3). 이런 경우에는, 심지어 두 플레이어가 서로의 위치를 알고 일부러 게임을 끝내려고 해도 끝낼 수 없다!
보드판의 모양이 주어질 때, 어떻게 움직여도 영원히 게임이 끝나지 않는 초기 위치의 경우의 수가 몇 가지가 있을지 구해보자.
입력
첫 번째 줄에 수풀의 수 N(2 ≤ N ≤ 50,000)과 오솔길의 수 M(1 ≤ M ≤ 500,000)이 공백으로 구분되어 주어진다.
두 번째 줄부터 M개의 줄에 걸쳐, u, v(1 ≤ u,v ≤ N, u ≠ v)가 공백으로 구분되어 주어진다. 이는 u번 수풀과 v번 수풀이 오솔길로 연결되어 있음을 의미한다.
출력
첫 번째 줄에 어떻게 움직여도 영원히 게임이 끝나지 않는 초기 위치의 경우의 수를 출력한다.
답이 32-bit형 정수(int)의 최대값보다 클 수 있음에 주의하자.
어떤 방식으로도 만날 수 없는 경우는 이분 그래프에서 나눠진 반반에 각자가 놓여있을때이다.
한 정점에서 시작해서 이어진 정점에 현재 정점과 다른 색으로 칠한다.
이렇게 다른 색 (이어진 정점)에 토끼와 사자가 각 위치하면 절대 만날수가 없다.
따라서 각 색의 카운트를 세서 곱하고 그 색의 반대 경우도 고려해서 *2를 한다.
만약 이분 그래프가 아니라면 어떤 방식에따라 만나게 될 경우도 있기 때문에 0을 출력하면 된다.
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;
int N, M;
vector<int> route[50001];
int visit[50001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
route[a].push_back(b);
route[b].push_back(a);
}
queue<pair<int,int> > que;
que.push({ 1,1 });
visit[1] = 1;
long long rabbit = 1;
long long lion = 0;
while (!que.empty())
{
int cur = que.front().first;
int color = que.front().second;
que.pop();
for (int i = 0; i < route[cur].size(); i++)
{
if (!visit[route[cur][i]])
{
visit[route[cur][i]] = color * -1;
if (color * -1 == 1)
rabbit++;
else
lion++;
que.push({ route[cur][i],color * -1 });
}
else
{
if (visit[route[cur][i]])
{
if (visit[route[cur][i]] == color)
{
cout << 0 << endl;
return 0;
}
}
}
}
}
cout << rabbit * lion * 2 << endl;
}
'Algorithm' 카테고리의 다른 글
[2018 홍익대학교 프로그래밍 경진대회] 16395번 파스칼의 삼각형 (0) | 2021.01.10 |
---|---|
[2018 홍익대학교 프로그래밍 경진대회] 16394번 홍익대학교 (0) | 2021.01.10 |
[2019 홍익대학교 프로그래밍 경진대회] 17835번 면접보는 승범이네 (0) | 2021.01.07 |
[2019 홍익대학교 프로그래밍 경진대회] 17830번 이진수씨의 하루 일과 (0) | 2021.01.05 |
[2019 홍익대학교 프로그래밍 경진대회] 17829번 222-풀링 (0) | 2021.01.05 |