[C/C++] 백준 #2673 교차하지 않는 원의 현들의 최대집합(깊이우선탐색)

일단 이 문제는 추천하는 알고리즘은 동적 계획법(Dynamic Programming)입니다.

저는 깊이우선탐색(Depth First Search)를 이용해서 문제를 풀었고, 경과시간은 4ms를 얻었네요.  아마 동적 계획법을 이용해서 풀면 더 나은 결과가 있었을 것이라고 생각은 합니다.

 

sample problem

 

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

 

제가 한 방법은 다음과 같습니다.

1) 모든 현들과 서로 교차하지 않는 현들을 구해서 그 결과를 비트 플래그로 저장 \(O(N^2)\)

2) 1번 현부터 시작해서 모든 현에 대해서

  2-1) 교차하지 않는 현들을 방문하여 최대 길이를 구한다.

 

이 프로그램은 원 위에 주어진 여러 개의 현(chord) 중에서 서로 교차하지 않는 최대 개수의 현을 찾는 문제를 해결하는 코드입니다. 이 문제는 조합 최적화 문제로, 동적 프로그래밍 및 비트 마스킹 기법을 활용해 해결됩니다. 각 부분을 자세히 살펴보겠습니다.

1. `getMaxChords` 함수
   - 입력
     - `ninter[]`: 각 현이 서로 교차하지 않는 현들을 비트 마스크로 나타낸 배열
     - `n`: 전체 현의 개수
     - `av`: 사용 가능한 현들을 나타내는 비트 마스크
     - `c`: 현재 검사 중인 현의 인덱스
   - 출력
     - 현재 비트 마스크 `av`로부터 시작해서 선택할 수 있는 최대 교차하지 않는 현의 개수를 반환
   - 구현   

int getMaxChords(long long ninter[], int n, long long av, int c)
{
    int max = 0;
    for(int i = c; i < n; i++)
    {
        if(!(av & (1LL<<i))) continue;
        int r = getMaxChords(ninter, n, av&ninter[i], i+1)+1;
        if(r > max) max = r;
    }
    return max;
}

     - `max` 변수를 초기화하고 `c`부터 `n`까지 순회하면서 사용 가능한 현(`av`)을 체크합니다.
     - 해당 현이 사용 가능하면(`if(!(av & (1LL<<i))) continue;`), 그 현을 선택한 후 나머지 가능한 현들에 대해 재귀적으로 최대 개수를 구합니다.
     - 반환 값에 1을 더하여(`+1`), 그 값을 최대값과 비교하여 갱신합니다.

2. `main` 함수

   - 구현 

int main()
{
    int n, chords[50][2];
    static long long ninter[50];
    
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if(a < b) chords[i][0] = a, chords[i][1] = b;
        else chords[i][0] = b, chords[i][1] = a;
        ninter[i] = 1LL<<i;
        for(int j = 0; j < i; j++)
        {
            if(chords[i][1] < chords[j][0] || chords[i][0] > chords[j][1] ||
                (chords[i][0] < chords[j][0] && chords[i][1] > chords[j][1]) ||
                (chords[i][0] > chords[j][0] && chords[i][1] < chords[j][1]))
            {
                ninter[i] |= 1LL<<j;
                ninter[j] |= 1LL<<i;
            }
        }
    }
    int ret = getMaxChords(ninter, n, (1LL<<n)-1, 0);
    printf("%d\n", ret);
}

     - `n`과 현의 양 끝점들을 입력받고, 각 현의 양 끝점을 정렬합니다.
     - `ninter` 배열을 초기화합니다. 각 현이 어떤 현들과 교차하지 않는지를 비트 마스크로 나타냅니다.
     - 모든 현 쌍을 비교하여 교차하지 않는 경우 비트 마스크를 갱신합니다.
     - `getMaxChords` 함수를 호출하여 서로 교차하지 않는 최대 개수의 현을 계산한 후 출력합니다.