백준 1707 이분그래프

문제 URL : https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

문제 접근법:

물감의 색이 2개만 주어졌다고 생각하고 어떤 노드에서 출발해서 그노드와 인접한 노드들간에 서로 다른색으로

색칠이 되어있다면 그것은 이분그래프라고 생각하면 됩니다.

쉽게 그림으로 설명해드리겠습니다.

 

 

이분 그래프

간단하게 1번노드에서 먼저 초록색을 색칠한다면 1번과 인접한 2,4번 노드에 노랑색을 색칠하고 또 2,4번과 인접한

5,6번에 초록색을 색칠하고 5,6번과 인접한 3번에 노란색을 색칠을하게 되면 인접한 노드들간의 색은 두가지로 표현되어도 서로 다른색을 갖고있으니 이분그래프라 할수있습니다.

그러나 예를들어 여기서 간선하나를 추가해서 그래프가 어떻게 달라지는지 보여드리겟습니다.

 

이분그래프가 아님

위의 사진을 보면 간선하나를 추가했는데 1,5번이 연결되었고 1,5번이 인접한 노드가 되어 서로 같은색을 공유하기때문에 이분그래프가 아니게 됩니다.

반대로 마지막 하나 더 예를 보여주자면

이분그래프

마찬가지로 간선 한개만 1,3번과 연결시켰지만 서로 인접한 노드들간의 색이 다르기때문에 이분그래프라 할수있습니다.

이렇게 간선이 어떻게 연결되어있느냐에 따라 이분그래프인지 아닌지 결정이 됩니다. 신기하죠?

 

그럼 인제 이문제를 풀어보겠습니다. 어떻게 풀었느냐?

저는 bfs를 이용했습니다. 

우선 입력으로 그래프형식을만들어주고 bfs를 돌아 색칠을 해줍니다.

여기서 중요한건 1번부터 n번 정점까지  bfs를 돌아야 합니다. 이유는 모든그래프가 서로 연결되어있을 거라는 보장은 없습니다.

 그래프가 따로 따로 그려져 있는경우도 있을수 있기에 이런식으로

연결되어 있지 않은 그래프지만 이분그래프

 

이것 또한 이분그래프 입니다. 만약 저둘중에 이분그래프 모양이 하나라도 존재하지 않는다면 이분그래프가 아니게 됩니다.

 

그럼 bfs를 어떻게 구현했는지 설명하겠습니다.

1번~n번 정점까지 bfs를 돌립니다. 색칠을 안한것이 있다면 우선 1번정점부터 색칠을 초록색을 색칠하게되고

인접한 노드 2,4번을 노랑색  으로 색칠합니다. 또다시  2,4번과 인접한노들 1,6,5를 보게되면 1번은 색칠이 되어있으면

색칠을 하진 않지만 색을 구분해봅니다. 색칠이 되어있다면 현재의 내색과 같은지 같으면 이분그래프가 아니므로 바로 false를 반환하면되고 같지않으면 6,5를 보고 색칠을 해줍니다. 이런식으로 3번까지 무사히 색칠해주고 다시 7번을 색칠을하고 9번까지 무사히 색칠해주면 이분그래프라는 것을 알게됩니다.

 

그럼 코드를 보여드리겠습니다.

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

#include <iostream> #include<cstdio> #include <algorithm> #include <vector> #include <cmath> #include <queue> using namespace std; vector<int> v[20000]; char visit[20001] = { 0 }; bool bfs(int idx) {     queue<pair<int,int>> q;     q.push({idx,1});          visit[1] = 1;     while (!q.empty()){         int cur = q.front().first;         int color = q.front().second;         q.pop();         for (int i = 0; i<v[cur].size(); i++)         {             int next = v[cur][i];             if (visit[next] == 0){//색칠이 안되어있다면 색칠해줘야함                 int nextcolor = (color == 1) ? 2 : 1;//현재 색칠한것이 1번으로 색칠했다면 2번으로 색칠하고 2번이면 1번으로 색칠 서로다르게                 visit[next] = nextcolor;                 q.push({next,nextcolor});             }             else//인접한 정점이 색칠이 되어있는경우             {                 if (visit[next] == color)//인접한 정점이 나와 같은색깔이라면 이분그래프가아님                      return false;             }         }     }     return true; } int main(void) {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     int test;     cin >> test;     while (test--){         int n, e;         cin >> n >> e;         for (int i = 1; i <= n; i++){             v[i].clear();             visit[i] = 0;         }         for (int i = 0; i < e; i++)         {             int x, y;             cin >> x >> y;             v[x].push_back(y);//양방향그래프를 만들어야함             v[y].push_back(x);         }         bool flag = true;         for (int i = 1; i <= n; i++)         {             if (visit[i] == 0){                 flag = bfs(i);             }             if (flag == false)//이분그래프가 아닌것이 발견되면 더이상 bfs를 돌릴필요가없음                 break;         }         if (flag)             cout << "YES" << "\n";         else             cout << "NO" << "\n";       } } Colored by Color Scripter

cs

 

설명은 여기까지입니다.

질문이나 모르는것이 있다면 언제든지 댓글을 이용해주시길 바랍니다.