[BOJ 15510 // C++] League of Overwatch at Moloco (Easy)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 15510번 문제인 League of Overwatch at Moloco (Easy)이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/15510 

15510번: League of Overwatch at Moloco (Easy)

15511번 문제에서 입력제한이 강해진 문제이다. 해당 문제의 풀이를 참고해 문제를 해결할 수 있다.

 

위와 같이 풀지 않더라도, 이 문제는 입력 제한이 강하므로 16명의 각 사람을 팀 A와 팀 B 둘로 나누는 모든 각 경우의 수에 대하여 두 사람 i와 j가 서로 다른 팀에 속해있는지를 전부 조사해보는 브루트포스 구현으로도 통과할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<int> G[17];
int dist[17];
bool chk = 1;

void dfs(int cur) {
	for (auto& x : G[cur]) {
		if (dist[x]) {
			if (((dist[cur] + dist[x]) & 1) == 0) chk = 0;
		}
		else {
			dist[x] = dist[cur] + 1;
			dfs(x);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	if (N == 1) {
		cout << "IMPOSSIBLE";
		return 0;
	}

	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	for (int i = 1; i <= N; i++) {
		if (dist[i]) continue;
		dist[i] = 1;
		dfs(i);
	}

	if (chk) cout << "POSSIBLE";
	else cout << "IMPOSSIBLE";
}