[C/C++] 백준 #2668 숫자고르기(순환구조 탐색)

이번 문제는 양면에 숫자가 적인 숫자 카드를 적절하게 골라서, 한면에 있는 숫자들 집합과 다른 한면에 있는 숫자들 집합이 같은 최대의 카드수를 찾아내야 합니다.

 

choicing number card

 

그래프 연결이 맞기는 하지만, 이것을 깊이 우선 탐색이라고 하기에는 적절하지 않아서, 순환구조 탐색이라는 말을 사용했습니다.

 

카드들의 앞에 있는 숫자는 모든 1부터 N까지 모든 숫자들이 있고, 뒤의 숫자들은 1부터 N까지 수중에 임의 수들이 적혀 있습니다.  여기에 적당한 카드들을 선택하면, 앞의 숫자들은 서로 겹치지 않기 때문에 뽑은 카드수만큼의 숫자들이 집합이 되지만, 뒤의 숫자는 겹치는 경우도 있을 수도 있죠.  그래서 같은 집합이 되려면, 각각의 뒤에 있는 숫자들이 다음 카드들을 가르키고 있고, 맨 처음 카드까지 순환을 이룬다면, 이 하나의 순환이 하나의 순환집합이 됩니다.  이 순환집합은 카드셋에 여러개가 있을 수 있으므로, 순환집합에 참여하지 않은 모든 카드들을 시작카드로 처리하면 됩니다.

 

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

 

#### 전역 변수 및 함수 선언

#include <stdio.h>

int isCircular(int q[], int v[], int c, int first)
{
    if(v[c]) return 0;
    v[c] = 1;
    if(q[c] == first) return 1;
    int r = isCircular(q, v, q[c], first);
    if(r) return r+1;
    v[c] = 0;
    return 0;
}

- `isCircular` 함수: 주어진 배열 `q`와 방문 여부를 기록하는 배열 `v`를 사용하여 순환 구조를 탐색합니다.
  - `q[]`: 주어진 배열, 각 인덱스의 값은 다음으로 이동할 인덱스를 나타냅니다.
  - `v[]`: 방문 여부를 기록하는 배열, 초기 값은 모두 0입니다.
  - `c`: 현재 인덱스.
  - `first`: 탐색 시작 인덱스.
  - 함수는 순환을 찾으면 1을 반환하고, 순환의 길이를 반환합니다. 순환을 찾지 못하면 0을 반환합니다.

#### 메인 함수

int main()
{
    int s, n;
    static int q[100000], v[100000], ans=0;
    scanf("%d",&n);
    for(int I=0; I<n; I++)
    {
        scanf("%d",&s); 
        q[I] = s-1;
    }
    for(int I=0; I<n; I++)
    {
        if(v[I]) continue;
        ans += isCircular(q, v, I, I);
    }
    printf("%d\n", ans);
    for(int I=0; I<n; I++)
    {
        if(v[I]) printf("%d\n", I+1);
    }
}

- `int s, n;`: `s`는 입력 값을 받을 변수, `n`은 배열의 크기입니다.
- `static int q[100000], v[100000], ans=0;`: 
  - `q[]`: 입력 값을 저장할 배열.
  - `v[]`: 방문 여부를 기록할 배열.
  - `ans`: 순환 구조에 포함된 원소의 개수를 저장할 변수.
- `scanf("%d",&n);`: 배열의 크기를 입력받습니다.
- `for(int I=0; I<n; I++)`: 배열 `q`에 값을 입력받아 저장합니다. 입력 값은 1-based index이므로 0-based index로 변환하여 저장합니다.
- `for(int I=0; I<n; I++)`: 배열 `q`를 순회하면서 아직 방문하지 않은 인덱스를 시작점으로 `isCircular` 함수를 호출합니다.
  - 순환 구조를 찾으면 그 길이를 `ans`에 더합니다.
- `printf("%d\n", ans);`: 순환 구조에 포함된 원소의 개수를 출력합니다.
- `for(int I=0; I<n; I++)`: 배열 `v`를 순회하면서 순환 구조에 포함된 인덱스를 출력합니다. 1-based index로 출력합니다.

### 요약
이 프로그램은 주어진 배열에서 순환 구조를 찾아 그 길이를 출력하고, 순환 구조에 포함된 원소들의 인덱스를 출력합니다. 순환 구조를 찾기 위해 재귀적으로 배열을 탐색하며, 방문 여부를 기록하여 이미 방문한 인덱스를 다시 방문하지 않도록 합니다.

 

제가 작성한 소스입니다.

//----------------------------------------------------------
//    baekjoon #2668 - Choicing numbers
//        - by Aubrey Choi
//        - created at 2019-11-08
//        - updated at 2024-06-04
//----------------------------------------------------------
#include <stdio.h>

int isCircular(int q[], int v[], int c, int first)
{
    if(v[c]) return 0;
    v[c] = 1;
    if(q[c] == first) return 1;
    int r = isCircular(q, v, q[c], first);
    if(r) return r+1;
    v[c] = 0;
    return 0;
}

int main()
{
    int s, n;
    static int q[100000], v[100000], ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&s); 
        q[i]=s-1;
    }
    for(int i=0;i<n;i++)
    {
        if(v[i]) continue;
        ans += isCircular(q, v, i, i);
    }
    printf("%d\n",ans);
    for(int i=0;i<n;i++)
    {
        if(v[i]) printf("%d\n", i+1);
    }
}