[BOJ] 12893번 : 적의 적 C++ 풀이

정말 간단한 그래프 탐색 문제이다. 나를 기준으로 친구들과는 적대적인 관계이지만, 친구의 친구와는 우호 관계라고 한다.
이를 만족하는 그래프인지 확인해야 하는데, 그래프가 순환하는 형태인지 확인하면 된다. 왜냐면 트리 구조일 경우에는 무조건적으로 위의 조건을 만족하기 때문이다.

자 그럼 그래프가 순환하는지 확인해보자. 현재 노드와 연결된 노드 중 이전에 방문한 적이 있음에도 나와 우호적인 관계로 표시된 노드가 있다면 그래프가 순환하는 상태라고 판단할 수 있다. 그래서 boolean 변수를 하나 두고, dfs 탐색에 조건문 하나를 추가해 이를 판별하도록 구현했다.

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 1000000000
#define MOD 1000000009
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
int N, M;
int visited[2010];
bool answer = true;
vector<int> adj[2010];

void dfs(int curr) {
    for (int next : adj[curr]) {
        if (visited[next] == -1) {
            if (visited[curr] == 1) visited[next] = 0;
            else visited[next] = 1;
            dfs(next);
        }
        else if (visited[next] == visited[curr]) answer = false;
    }
}

void init() {
    memset(visited, -1, sizeof(visited));
    cin >> N >> M;
    for (int i=0; i<M; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for (int i=1; i<=N; i++) {
        if (visited[i] == -1) {
            visited[i] = 1;
            dfs(i);
        }
    }
    cout << answer << '\n';
} 

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
}