1일차 (월) : 1707번, 이분그래프 (G4)

문제 : 이분 그래프를 판단하는 문제이다. 이산수학에서 학습한 내용을 적용하여 풀이법을 쉽게 생각할 수 있었다. 이분 그래프는 인접한 정점을 서로 다른 색으로 구분하여 2가지의 색으로 나타낼 수 있는지 확인하면 된다.

풀이과정

1. 테스트 케이스가 존재하므로 각각의 케이스를 처리하는 fun() 함수를 만들어서 처리
2. 그래프의 대한 정보를 통해 bfs로 각각의 정점의 색을 1과 2로 구분하기로 결정
3. 정점이 1~V까지 나타남으로 1을 기준으로 시작하여 색을 구분하며 진행
4. 예제가 통과하는 것을 확인한 후, 1차 제출
5. 그러나 그래프가 연결되있지 않아 모든 정점을 확인하지 않는 반례가 발생
6. 모든 정점 방문을 확인하는 코드 추가 후, 2차 제출
7. 정답

풀이 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int change_color(int color) {
    if (color==1)
        return 2;
    else
        return 1;
}

int bfs(vector<vector<int>>& graph, int v, int e) {
    vector<int> visited(v + 1, 0);
    queue<pair<int, int>> q;
    q.push({ 1, 1 });
    visited[1] = 1;

    int flag = 1;

    y :
    while (q.size()) {
        int now = q.front().first;
        int color = q.front().second;
        int nxt_color = change_color(color);
        q.pop();

        for (int nxt : graph[now]) {
            if (visited[nxt] == color) {
                flag = 0;
                goto x;
            }
            else if (visited[nxt] == nxt_color)
                continue;
            else {
                visited[nxt] = nxt_color;
                q.push({ nxt, nxt_color });
            }
        }
    }

    x :

    if (flag == 0)
        return 0;
    
    int i = 1;
    for (i; i <= v; i++)
    {
        if (visited[i] == 0)
        {
            q.push({ i, 1 });
            visited[i] = 1;
            goto y;
        }
    }

    return 1;
}

void fun() {
    int v, e;
    cin >> v >> e;
    vector<vector<int>> graph(v + 1);

    for (int i = 0; i < e; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }

    cout << (bfs(graph, v, e) ? "YES\\n" : "NO\\n");
}

int main(void) {
    int k;
    cin >> k;
    while (k--) fun();
}

반례