(3) [C++, Java] 백준 No.1707 : 이분 그래프

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/398

# C++(색을 모두 칠해준 다음, 모든 간선의 양끝 정점 색을 비교함 => 비효율적)

#include<iostream>
#include<vector>

using namespace std;

vector<int> arr[20001];   // 인접 리스트
int color[20001];         // 중복방문을 막기위한 check 배열, 단 방문시 색을 저장함
void dfs(int node, int c);// DFS탐색을 진행하며 1, 2를 번갈아가며 정점에 색칠하는 함수

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 테스트 케이스의 개수 입력받기
    int k;
    cin >> k;

    while(k--){
        // 정점의 개수 v와 간선의 개수 e입력받기
        int v, e;
        cin >> v >> e;

        // 인접리스트 및 check 배열인 color 초기화
        for (int i = 1; i <= v; i++) {
            arr[i].clear();
            color[i] = 0;
        }

        // 연결된 두 정점에 대한 정보를 입력받아 인접 리스트 만들기
        for (int i = 0; i < e; i++){
            int a, b;
            cin >> a >> b;
            arr[a].push_back(b);
            arr[b].push_back(a);
        }

        // 모든 노드에 빨강, 파랑으로 번갈아가며 색 칠해주기
        // *그래프가 2개 이상으로 이루어진 것일 수 있으므로 시작점을 바꿔가면서도 탐색을 해줘야함.
        for (int i = 1; i <= v; i++){
            if (color[i] == 0){
                dfs(i, 1);
            }
        }

        // 모든 간선의 양끝 정점 색이 같은게 있나 비교
        bool is_bipartite = true;

        for (int i = 1; i <= v; i++){
            for (int j = 0; j < arr[i].size(); j++){
                if (color[i] == color[arr[i][j]]){
                    is_bipartite = false;
                }
            }
        }

        if (is_bipartite)
            cout << "YES" << "\n";
        else
            cout << "NO" << "\n";
    }
}

void dfs(int node, int c){
    color[node] = c;
    //cout << node << " ";

    for (int i = 0; i < arr[node].size(); i++){
        if (color[arr[node][i]] == 0){
            dfs(arr[node][i], 3-c);
        }
    }
}

 

# C++(탐색을 파고들 때 마다 이전노드와 현재노드의 색을 비교함 => 효율적)

#include<iostream>
#include<vector>

using namespace std;

vector<int> arr[20001];   // 인접 리스트
int color[20001];         // 중복방문을 막기위한 check 배열, 단 방문시 색을 저장함
bool dfs(int node, int c);// DFS탐색을 진행하며 1, 2를 번갈아가며 정점에 색칠하는 함수

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 테스트 케이스의 개수 입력받기
    int k;
    cin >> k;

    while(k--){
        // 정점의 개수 v와 간선의 개수 e입력받기
        int v, e;
        cin >> v >> e;

        // 인접리스트 및 check 배열인 color 초기화
        for (int i = 1; i <= v; i++) {
            arr[i].clear();
            color[i] = 0;
        }

        // 연결된 두 정점에 대한 정보를 입력받아 인접 리스트 만들기
        for (int i = 0; i < e; i++){
            int a, b;
            cin >> a >> b;
            arr[a].push_back(b);
            arr[b].push_back(a);
        }

        // 모든 노드에 빨강, 파랑으로 번갈아가며 색 칠해주기
        // *그래프가 2개 이상으로 이루어진 것일 수 있으므로 시작점을 바꿔가면서도 탐색을 해줘야함.
        // 동시에 dfs함수는 다음 정점이 같은 색이면 false를 반환하게 되는데, 그러면 이분그래프가 아님 처리.
        bool is_bipartite = true;

        for (int i = 1; i <= v; i++){
            if (color[i] == 0){
                if (dfs(i, 1) == false){
                    is_bipartite = false;
                    break;
                }
            }
        }

        if (is_bipartite)
            cout << "YES" << "\n";
        else
            cout << "NO" << "\n";
    }
}

bool dfs(int node, int c){
    color[node] = c;
    //cout << node << " ";

    for (int i = 0; i < arr[node].size(); i++){
        // 이때에 해당되면 다음 노드는 당연히 다른 색으로 칠해질 것임
        if (color[arr[node][i]] == 0){
            if (dfs(arr[node][i], 3-c) == false)
                return false;
        }
        // 이때에 해당되면 다음 노드는 다른색일수도 같은 색일 수도 있음
        else if (color[node] == color[arr[node][i]])
            return false;
    }
    return true;
}

# Java

import java.util.*;

public class Main {
    public static void dfs(ArrayList<Integer>[] a, int[] color, int x, int c) {
        color[x] = c;
        for (int y : a[x]) {
            if (color[y] == 0) {
                dfs(a, color, y, 3-c);
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n+1];
            for (int i=1; i<=n; i++) {
                a[i] = new ArrayList<Integer>();
            }
            for (int i=0; i<m; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                a[u].add(v);
                a[v].add(u);
            }
            int[] color = new int[n+1];
            boolean ok = true;
            for (int i=1; i<=n; i++) {
                if (color[i] == 0) {
                    dfs(a, color, i, 1);
                }
            }
            for (int i=1; i<=n; i++) {
                for (int j : a[i]) {
                    if (color[i] == color[j]) {
                        ok = false;
                    }
                }
            }
            if (ok) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }

    }
}