99클럽 코테스터디 17일차 TIL 사자와 토끼

사자와 토끼

BOJ Gold 1 이분탐색
문제링크

문제 설명

문제 풀이

처음에 BFS 로 시뮬레이션 느낌으로 구현했는데 시간초과가 났다.

문제를 푸는 과정에서 잠깐 생각했던 이분그래프 로직으로 다시 짜봤는데, 성공적으로 통과했다.

노드를 색칠한다고 생각하고, 하나의 노드를 빨간색으로 칠했다면, 그 노드와 연결되어 있는 모든 노드는 파란색으로 칠하는 로직이다.

구현

#include <iostream>
#include <vector>
#define MAXN 50005

using namespace std;

// 수풀의 수, 오솔길의 수
int N, M, res=0;
vector<vector<int>> fld(MAXN);
int visited[MAXN];

void dfs (int cur) {
    if (visited[cur] == 0) {
        visited[cur] = 1;
        res++;
    }
    for (int i=0; i<fld[cur].size(); i++) {
        int next = fld[cur][i];
        if (visited[next] == 0) {
            if (visited[cur] == 1) {
                visited[next] = 2;
            }
            else if (visited[cur] == 2) {
                visited[next] = 1;
                res++;
            }
            dfs(next);
        }
    }
}

bool isBinary() {
    for (int i=1; i<=N; i++) {
        for (int j=0; j<fld[i].size(); j++) {
            if (visited[i] == visited[fld[i][j]]) return false;
        }
    }
    return true;
}

int main () {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    cin >> N >> M;

    // 수풀끼리 연결
    for (int i=0; i<M; i++) {
        int u, v;
        cin >> u >> v;
        fld[u].push_back(v);
        fld[v].push_back(u);
    }
    for (int i=1; i<=N; i++) {
        visited[i] = 0;
    }

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

    if (isBinary()) cout << res * (N-res) * 2 << "\n";
    else cout << 0 << "\n";

    return 0;
}

 

회고

이틀전에 풀이했던 문제는 시간복잡도를 처음부터 계산해 설계과정에서 시간초과가 날 지 테스트 했었는데, 이번에는 그러지 못했다.

BFS 와 DFS 시간 복잡도는 $ O(V + E) $ 이므로 다음 풀이부터는 고려해서 작성해야 할듯.