챕터6-4. 그래프 | 문제풀이(1) - DFS, BFS 탐색응용

연결요소(Connected Component)

# 개념
- 연결요소란, '간선으로 연결된 정점들'이고, 이는 그래프를 구성하는 요소가 된다.
- 아래의 경우 1개 혹은 2개의 그래프로 볼 수 있으며, 연결요소가 2개인 것은 변함이 없다.

# 연결요소의 개수를 구하는 문제
- https://www.acmicpc.net/problem/11724 
- 연결 요소의 개수를 구하는 것은 DFS나 BFS 탐색을 이용해서 구할 수 있다.
   1) 정점을 차례대로 시작점으로 두고 DFS혹은 BFS를 진행하는데, check배열이 true로 방문한 상태이면 탐색을 진행하지 않는다.
   2) DFS 혹은 BFS를 수행한 횟수를 세어주면 그것이 곧 연결요소의 개수가 된다.

이분 그래프(Bipartite Graph)

# 개념
- 그래프에서 A에 포함되어 있는 정점끼리 연결된 간선이 없고, B에 포함되어 있는 정점끼리 연결된 간선이 없으며
   모든 간선의 한 끝 점은 A에, 다른 끝 점은 B에 있어서 이렇게 A와 B로 나눌 수 있으면 이분 그래프라고 한다.

연결요소가 1개인 경우에서 보여지는 이분 그래프

연결요소가 2개인 경우에서 보여지는 이분 그래프

# 주어진 그래프가 이분 그래프인지 아닌지 확인하는 문제
- https://www.acmicpc.net/problem/1707
- 그래프가 이분 그래프인지 아닌지 확인하는 것은 DFS나 BFS 탐색을 이용하면 가능하다.
   1) BFS 혹은 DFS를 활용하여 한 노드를 방문할 때마다 파랑(1), 빨강(2)을 번갈아가며 색칠해준다. 방문하지 않은곳은 0.
       * 연결요소가 2개 이상인 경우가 있을 수 있으므로 시작점을 바꿔가며 모든 정점에 대해 수행해줘야 한다.
   2) 간선으로 연결된 두 정점에 칠해진 색이 같으면 이분 그래프가 아니고, 모두 다르면 이분 그래프이다.
   * 주의할 점 : check배열의 역할이 조금 달라져야 한다. 방문한 경우 색을 칠하는 역할이 추가되어 이름도 color로 바꿔쓴다.
   check[i] = 0 (아직 방문안함)
                    = 1 (방문함)

   color[i] = 0 (아직 방문안함)
                    = 1 (방문함, 파랑)
                    = 2 (방문함, 빨강)
   위의 이유로 코드에서 dfs 혹은 bfs함수에 파라미터를 하나 추가했는데 c : 어떤 색을 칠할 것인지를 의미한다.
   c-3은 이전것이 1이면 다음 것은 2로, 이전것이 2이면 다음 것은 1로 되도록 하기 위함

* 이 문제는 문제 해결과정에서 사용하는 인접리스트 혹은 color 배열을 초기화 하지 않으면 정답처리가 안되므로 주의!

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

@ 구현방식1
- 탐색 알고리즘으로 모든 정점에 색깔을 매긴뒤, 모든 간선의 양 끝 노드의 색을 비교하는 방식

@ 구현방식2(효율적인 이 방식이 좋음)
- 탐색 알고리즘으로 정점에 색깔을 매기는 과정에서 중간에 간선의 양 끝 노드의 색을 비교하는 방식으로 효율적임.
- 탐색 함수를 void 형이 아닌 bool 타입을 반환하는 것으로 구현해야함.
- 탐색 함수 내에서 return true, return false를 적절한 위치에 배치해야하며,
   조건문을 하나 더 추가해서 다음 노드의 color가 0이 아닌경우에 다음 노드와의 색을 계속 비교하도록 해야한다.

사이클과 관련된 문제

아래 문제들의 특징은 모든 정점이 다음 정점을 가진다는 점이다.
이럴 때의 특성으로는 탐색은 한번 시작되면 방문했던 점을 만날 때 까지 진행된다.

문제유형1. 한 방향(반시계 혹은 시계)으로 가는 간선 혹은 루프만 있는 경우는 이미 방문한걸 재방문하면 무조건 사이클.

문제유형2. 한 방뱡으로만 가는 간선이 아닌 경우 이미 방문한걸 재방문하면 같은 탐색에서 재방문하게 된 것인지 체크해야함.
                     같은 탐색 내에서 재방문 한 것이면 사이클이지만 다른 탐색에 의해 방문한 것을 재방문 한 것이라면 사이클이 아님

# 순열사이클의 개수를 찾는 문제
- https://www.acmicpc.net/problem/10451
- 단방향그래프 이므로 '순열사이클'의 개수는 '연결요소'의 개수와 같다.(연결요소의 개수를 찾는 문제와 같은 방법으로 해결가능)
- 단 두가지 단순화 시킬 수 있는 점이 있다.
   1) 단방향 간선이므로 인접행렬을 이용하는 것은 비효율적이고, 
      하나의 정점은 다음 정점을 단 한 개만 가지므로 인접리스트까지도 사용할 필요가 없다.
      따라서, 원소 1개만을 가지는 인접리스트 정도로 구현하면 된다.
      즉, 그래프를 저장할 때는 a[i] = ㅁ 일차원 배열 정도만 필요하다.
   2) dfs혹은 bfs함수 내에 존재하는 다음정점을 찾기위한 for문 혹은 while문은 필요가 없어진다.
       dfs(x)로 탐색을 시작하면 a[x]가 다음 정점이 되기 때문에.
- 위와같이 문제를 단순화 해주고, 탐색의 시작점을 바꿔가며 탐색이 진행된 횟수를 세어주면 된다.
   (단, 한번 방문했던 것에 대해서는 탐색을 시행하지 않는다.)
- ex) 1  2  3  4  5  6  7  8
          3  2  7  8  1  4  5  6

사이클이 3개

- ex) 1  2  3  4  5  6  7  8  9  10
          2  1  3  4  5  6  7  9  10  8

사이클이 7개

- dfs를 비재귀 함수로 바꿔서도 구현해보자. 

while(check[node] == false){
    check[node] = true;
    node = arr[node];
}

 

# 수열에서 반복되는 부분을 제외했을 때, 수열에 남게되는 수들의 개수를 구하는 문제
- https://www.acmicpc.net/problem/2331
- 차례로 탐색을 진행하여 check배열에 방문한 순서를 적어준다.
   check배열에 0과 1만 저장하는 것 대신, 방문하지 않았을 땐 0을, 방문했을 땐 방문한 순서를 저장한다.
- 다음 정점을 방문했는데 check가 0이 아니라면 사이클이 발생한 것이고, 그 정점이 가지고 있는 check값에서 1을 빼주면
   문제에서 원하는 답을 구할 수 있다.
- 이 문제는 그래프를 다 저장해 놓은 상태에서 진행하는 것이 아니라 다음 정점을 찾아가며 탐색을 진행한다.
- 단방향 그래프이므로 재귀호출을 사용하지 않고도 간단히 구현할 수 있다.
   비재귀 방식과 재귀 방식 모두 구현해보자.

A = 57, P = 2일 때의 수열

# 어떤 조에도 속하지 않는 사람의 수를 세는 문제 (사이클의 크기를 구하는 방법)
- https://www.acmicpc.net/problem/9466
- 문제요약 : 팀을 이루지 못한 사람의 수를 구하시오
- ex)
  i     : 1  2  3  4  5  6  7
A[i] : 3  1  3  7  3  4  6

   case 1) 팀을 이룰 수 있는 첫 번째 경우, 사이클의 크기가 1인 경우
   i == A[i] 일 때

  case 2) 팀을 이룰 수 있는 두 번째 경우, 사이클의 크기가 k인 경우
   P1 -> P2, P2->P3,,,, Pk->P1 일 때

사이클의 크기를 구하는 것이 문제의 핵심인데, 사이클의 크기를 구하는 방법은 아래와 같다.
- 방문한 순서를 저장해 두었다가 이미 방문한 것을 방문했을 때 이를 사용하여 사이클의 크기를 구할 수 있다.

비사이클 부분은 알아서 제거된 상태로 계산됨

사이클이라는 것은 어떻게 알 수 있을까?
이전 문제들까지는 방문했던 것을 다시 재방문 하려고 할 때 사이클이라는 것을 인식하였다.
그것은 독립된 루프 혹은 한방향(시계, 반시계)으로만 향하는 간선들로만 이루어진 그래프 였기 때문에 가능했는데,
이 문제는 상황이 다르다. 이 문제는 간선이 한방향으로만 향하지 않기 때문에 확인해줘야 할 것이 하나 추가된다.
"방문했던 것을 다시 재방문 하려고 할 때" && "재방문 하려는 노드가 이번 탐색의 경로에 포함되어 있는지"를 확인해야한다.

시작점이 1일때 탐색경로(3번 정점에서 크기가 1인 사이클 발견.)

시작점이 2일때 탐색경로(재방문 하려고 했지만 다른 탐색에서 방문한 정점을 찾았으므로 사이클 아님)

시작점이 3일때 탐색경로(이미 방문한 점이므로 탐색 X)

시작점이 4일때 탐색경로(동일한 탐색에서 이미 방문한 점을 찾았으므로 사이클 발견)

시작점이 5일때 탐색경로(다른 탐색에서 방문한 정점을 찾았으므로 사이클 아님)

그래서 이번 문제해결을 위해 필요한 것을 간단하게 요약하자면,
1) 정점을 방문할 때, 방문한 순서를 기록한다.=> 코드상에서 check 배열
   - 다음 탐색이 시작될 때 이전 cnt를 이어서 붙여줘도 되지만,
   - 이미 방문한 정점을 재방문했을 때 cnt의 차만 구하면 되므로 그냥 탐색마다 1로 시작해서 번호를 붙여줘도 된다.
2) 정점을 방문할 때,  몇번째 탐색에 의해 방문하는 것인지 기록한다. => 코드상에서 which_search 배열