[BOJ] 1707 : 이분 그래프

문제 링크

1707번: 이분 그래프 (acmicpc.net)

1707번: 이분 그래프

풀이

처음 떠올린 내 아이디어는 이렇다. DFS를 이용해 탐색하면서 인접한 정점은 현재 내가 있는 정점과 다른 그룹에 정점 번호를 집어 넣는다. 그리고 그룹에 새로운 정점이 들어올 때 마다 같은 그룹에 있는 앞서 들어온 정점들과 인접한지 체크한다.

그렇게 짠 코드가 아래의 코드이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
int T;
int V, E;
const int MAX_N = 20000 + 5;
int visited[MAX_N];
vector<int> Edge[MAX_N];
vector<int> group[2];
bool check_;
void dfs(int now , int idx) {
    group[idx].push_back(now);
    visited[now] = 1;
    for (int i = 0; i < group[idx].size() - 1; i++) {
        if (find(Edge[now].begin(), Edge[now].end(), group[idx][i]) != Edge[now].end()) {
            check_ = true;
            return;
        }
    }
    for (int i = 0; i < Edge[now].size(); i++) {
        int next = Edge[now][i];
        if (!visited[next]) {
            dfs(next, (idx + 1) % 2);
        }
    }
    return;
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    while (T--) {
        for (int i = 0; i <= V; i++) {
            Edge[i].clear();
        }
        memset(visited, 0, sizeof(visited));
        group[0].clear();
        group[1].clear();
        check_ = false;
        cin >> V >> E;
        int from, to;
        for (int i = 0; i < E; i++) {
            cin >> from >> to;
            Edge[from].push_back(to);
            Edge[to].push_back(from);
        }
        bool chk = false;
        for (int i = 1; i <= V; i++) {
            if (!visited[i]) {
                dfs(i, 0);
                if (check_ == true) {
                    cout << "NO\n";
                    chk = true;
                    break;
                }
            }
        }
        if (!chk) {
            cout << "YES\n";
        }
    }
    return 0;
}
 
 

아이디어는 괜찮다고 생각했는데 메모리 초과가 나버렸다. Edge 벡터에 visitied 배열 그리고 group 이라는 벡터까지

너무 많은 배열을 만들어서 그런 것 같다. 그런데 이 아이디어 외에는 떠오르는 아이디어가 없어 한참 고민하다 결국

다른 분의 코드를 참고했다.

참고한 링크

https://jdselectron.tistory.com/51

[백준 1707, c++] 이분 그래프(bfs,dfs)

이분의 논리는 결국은 나랑 똑같았다. 나는 정점을 각 그룹에 집어 넣었고 이 분은 정점에 색칠한다는 느낌으로 visited배열에 1은 빨강 2는 파랑으로 구분했다.

조금만 더 생각했더라면 충분히 내 힘으로 구현할 수 있었다는 아쉬움이 남는다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
int T;
int V, E;
const int MAX_N = 20000 + 5;
int visited[MAX_N];
vector<int> Edge[MAX_N];
 
void dfs(int now, int color) {
    visited[now] = color;
    for (int i = 0; i < Edge[now].size(); i++) {
        int next = Edge[now][i];
        if (!visited[next]) {
            if (color == 1)
                dfs(next, 2);
            else if (color == 2)
                dfs(next, 1);
        }
    }
    return;
}
 
bool is_Bipartite() {
    for (int i = 1; i <= V; i++) {
        for (int j = 0; j < Edge[i].size(); j++) {
            if (visited[i] == visited[Edge[i][j]])
                return false;
        }
    }
    return true;
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    while (T--) {
        for (int i = 0; i <= V; i++) {
            Edge[i].clear();
        }
        memset(visited, 0, sizeof(visited));
        cin >> V >> E;
        int from, to;
        for (int i = 0; i < E; i++) {
            cin >> from >> to;
            Edge[from].push_back(to);
            Edge[to].push_back(from);
        }
        for (int i = 1; i <= V; i++) {
            if (!visited[i])
                dfs(i,1);
        }
        if (is_Bipartite())
            cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}