[BOJ][1707] 이분 그래프

1. 문제 링크

https://www.acmicpc.net/problem/1707

2. 사용 알고리즘

DFS

3. 풀이

방문하지 않은 정점 0, 첫 번쨰 그룹 정점 1, 두 번째 그룹 정점 2로 저장

1) 1번 정점부터 차례대로 DFS 탐색 (BFS도 가능)

2) 방문하는 정점마다 1과 2를 번갈아가면서 저장

3) 다음 정점이 이미 방문한 정점인 경우

• 현재 정점과 같은 값이 저장되어 있으면 이분 그래프 X

• 현재 정점과 다른 값이 저장되어 있으면 이분 그래프 O

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/1707.cpp

#include <iostream>
#include <vector>

using namespace std;

vector<int> vec[20003];
int check[20003];
bool ans;

void dfs(int num, int val) {
    check[num] = val;
    int len = vec[num].size();
    for(int i = 0; i < len; ++i) {
        if(check[vec[num][i]] == 0) dfs(vec[num][i], 3 - val);
        else if(check[vec[num][i]] == val) ans = false;
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int k; for(cin >> k; k--;) {
        int v, e; cin >> v >> e;
        for(int i = 1; i <= v; ++i) {
            vec[i].clear();
            check[i] = 0;
        }
        ans = true;
        for(int i = 0; i < e; ++i) {
            int a, b; cin >> a >> b;
            vec[a].push_back(b); vec[b].push_back(a);
        }
        for(int i = 1; i <= v; ++i) {
            if(check[i] == 0) dfs(i, 1);
        }
        cout << (ans ? "YES" : "NO") << "\n";
    }
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/1707.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<Integer>[] arr = new ArrayList[20003];
    static int[] check = new int[20003];
    static boolean ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k; for(k = Integer.parseInt(br.readLine()); k-- > 0;) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            for(int i = 1; i <= v; ++i) {
                arr[i] = new ArrayList<>();
                check[i] = 0;
            }
            ans = true;
            for(int i = 0; i < e; ++i) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                arr[a].add(b); arr[b].add(a);
            }
            for(int i = 1; i <= v; ++i) {
                if(check[i] == 0) dfs(i, 1);
            }
            System.out.println(ans ? "YES" : "NO");
        }
    }

    public static void dfs(int num, int val) {
        check[num] = val;
        int len = arr[num].size();
        for(int i = 0; i < len; ++i) {
            if(check[arr[num].get(i)] == 0) dfs(arr[num].get(i), 3 - val);
            else if(check[arr[num].get(i)] == val) ans = false;
        }
    }
}