M'S Blog

M'S Blog

WWDC20 student challenge Winner!

Graph - 이분 그래프

1 분 소요

이분 그래프란?

  • 그래프를 위의 그림처럼 왼쪽과 오른쪽(A와 B)으로 나눌 수 있는 그래프.
  • 왼쪽에 포함된 정점끼리 연결 된 간선이 없고, 오른쪽에 포함된 정점끼리 연결 된 간선이 없다.
  • 쉽게 말해서 편 가르기 다.

이분 그래프 찾아내기

  • DFS와 BFS를 이용한다.

    • 정점을 방문 할 때 마다 __번갈아__가면서 분홍색과 보라색을 칠한다고 했을 때, 이분 그래프라면 6번의 그림처럼 완벽히 분홍색인 부분과 보라색인 부분으로 나뉘어진다.
    • 서로 연결된 정점끼리는 다른 색을 가지고 있다.

    하지만, 이분 그래프가 아니라면

    • 6번의 상황을 보자면 정점 6번에서 더 이상 갈 수 있는 곳이 있는지 확인한다.
      • 이때, 정점 6번에 연결된 정점은 3번과 2번인데, 둘 다 이미 방문한 적이 있는 곳이다. 그래서 더 이상 방문을 진행하지 않는다.
      • 색을 확인 해보면(이분 그래프는 방문하지 않아도 색 확인이 가능하다) 정점 3이 정점 6과 색이 같은 것을 알 수 있다. 따라서, 연결된 정점이 같은 색을 가지고 있으므로 이분 그래프가 아니다.

이분그래프 문제

  • 문제

    백준 1707번 - 이분 그래프

  • 풀이

    • dfs 함수 부분

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      bool dfs(int v, int c) {
          color[v] = c;
       
          for (int i = 0; i < list[v].size(); i++) {
              int next = list[v][i];
              if (color[next] == 0) {
                  if (!dfs(next, 3 - c)) {
                      return false;
                  }
              }
              else if (c == color[next]) {
                  return false;
              }
          }
       
          return true;
      }
      		cs
      • 방문 여부를 파악하기 위해 bool 값을 가지는 check라는 배열을 둔 것이 아닌 color라는 배열을 사용했다.
      • color의 값이 0 : 방문 x
        • color의 값이 1 : group1
      • color의 값이 2 : group2
      • 3-c를 사용한 이유는, color의 값을 구분하기 위해 사용한 1과 2의 합이 3이기 때문이다.
      • 현재 정점이 group1에 속한 경우에 다음 정점은 group2에 속해야 하기 때문에 3-1의 값인 2가 color에 저장된다.

    • main 함수 부분

    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
    int main() {
     
        int test;
     
        scanf("%d", &test);
     
        while (test--) {
     
            memset(list, 0, sizeof(list));
            memset(color, 0, sizeof(color));
     
            int v, e;
     
            scanf("%d %d", &v, &e);
     
            int n, m;
     
            for (int i = 0; i < e; i++) {
                scanf("%d %d", &n, &m);
                list[n].push_back(m);
                list[m].push_back(n);
            }
     
            bool ok = true;
            for (int i = 1; i <= n; i++) {
                if (color[i] == 0) {
                    if (dfs(i, 1) == false) {
                        ok = false;
                    }
                }
            }
            printf("%s\n", ok ? "YES" : "NO");
     
        }
     
        return 0;
    }
    		cs
    • 32 : 출력에는 3항 연산자를 이용했다.

    가능한 실수- 처음에는 24~32 말고

    1
    dfs(1,1) ? printf("YES\n") : printf("NO\n");
    		cs

    위의 코드로 작성했다.
    하지만 문제에서 제시한 예시는 정상적인 출력을 보였으나, 답안을 제출한 결과는 '틀렸습니다' 였다.
    테스트 케이스 중에 연결 요소가 하나가 아닌 그래프가 있는 것 같아서(연결 요소에 대한 설명은 여기서) 새로운 연결 요소에서도 탐색을 시작 할 수 있도록 코드를 작성하여 제출했더니 통과되었다.

    • 전체 코드

      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
      #include <cstdio>
      #include <vector>
      #include <cstring>
       
      using namespace std;
       
      vector<int> list[20001];
      int color[20001];
       
      bool dfs(int v, int c) {
          color[v] = c;
       
          for (int i = 0; i < list[v].size(); i++) {
              int next = list[v][i];
              if (color[next] == 0) {
                  if (!dfs(next, 3 - c)) {
                      return false;
                  }
              }
              else if (c == color[next]) {
                  return false;
              }
          }
       
          return true;
      }
       
      int main() {
       
          int test;
       
          scanf("%d", &test);
       
          while (test--) {
       
              memset(list, 0, sizeof(list));
              memset(color, 0, sizeof(color));
       
              int v, e;
       
              scanf("%d %d", &v, &e);
       
              int n, m;
       
              for (int i = 0; i < e; i++) {
                  scanf("%d %d", &n, &m);
                  list[n].push_back(m);
                  list[m].push_back(n);
              }
       
              //dfs(1,1) ? printf("YES\n") : printf("NO\n");
       
              bool ok = true;
              for (int i = 1; i <= n; i++) {
                  if (color[i] == 0) {
                      if (dfs(i, 1) == false) {
                          ok = false;
                      }
                  }
              }
              printf("%s\n", ok ? "YES" : "NO");
          }
       
          return 0;
      }
      		cs





아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고