[CODEGROUND] 김씨만 행복한 세상

DFS로 문제를 풀었다.

DFS는 역시 queue이다!!

queue에 아직 visit되지 않은 node를 넣고 돌린다.

하지만 여기서는 한 가지의 조건이 더 붙는다.

바로 A와 A, B와 B가 함께 살지 않는 조건이다.

따라서 문제는 아주 직관적으로 풀었다.

people이라는 곳에 first에 visit를 체크하고

second에 A와 B를 구별했다.

만약 people에 방문한 적이 있다면 A와 B중 무엇인지 결정이 되어있기 때문에

방문한 마을의 people type과 현재 마을의 people type을 비교해서 같으면 함께 살수 없다.

#include <iostream> #include <fstream> #include <vector> #include <queue> #include <algorithm> #include <functional> using namespace std; #define A 0 #define B 1 int result; vector<int> people; vector < vector < int > > village; queue<int> village_index; void check_village() { while (!village_index.empty()) village_index.pop(); village_index.push(1); people[1] = A; while (!village_index.empty()) { int index = village_index.front(); village_index.pop(); int people_type = people[index]; for (int j = 0; j < village[index].size(); j++) { if (people[village[index][j]] == -1) { people[village[index][j]] = people_type ^ 1; village_index.push(village[index][j]); } else if (people[village[index][j]] == people_type) { result = 0; return; } } } } int main() { int for_count, village_count, edge_count, start, end; cin >> for_count; for (int i = 1; i <= for_count; i++) { cin >> village_count >> edge_count; village = vector < vector < int > > (village_count + 1); people = vector<int>(village_count + 1, -1); while (edge_count--) { cin >> start >> end; village[start].push_back(end); village[end].push_back(start); } result = -1; check_village(); cout << "Case #" << i << endl; if (result == -1) cout << 1 << endl; else cout << 0 << endl; } }