BOJ 8907 네온 사인 & BOJ 17275 부족 전쟁 풀이

작성일 | In

　네온 사인과 부족 전쟁은 N 제한에 차이가 있을 뿐, 거의 완전히 동일한 문제이므로, 이 문제에서는 네온 사인의 풀이만 다루도록 하겠습니다.

　문제 설명

　N개의 꼭짓점과, 두 꼭짓점을 연결하는 N*(N-1)/2개의 튜브가 있습니다. 튜브는 빨간색/파란색 중 하나이고, 모든 튜브의 색상이 주어졌을 때, 단색 삼각형의 개수를 구하는 문제입니다.

github

　위 사진을 예로 들면, 단색 삼각형의 개수는 1, 3, 5번 꼭짓점으로 구성된 빨간 삼각형, 2, 3, 4번으로 구성된 파란 삼각형으로 총 2개입니다.

　풀이

　이 문제에 있어 가장 중요한 관찰은, 빨간 삼각형의 개수와 파란 삼각형의 개수를 각각 구하는 것이 아닌, 두 종류의 삼각형의 개수의 합을 구하는 문제라는 점입니다. 이렇게 되면, 문제를 ‘단색 삼각형의 개수 찾기’에서 ‘전체 삼각형의 개수에서 단색 삼각형이 아닌 삼각형의 개수 찾기’로 환원할 수 있습니다. 일단 전체 삼각형 개수는 N개의 꼭짓점 중 3개의 꼭짓점을 고르는 경우의 수이니, N(N-1)(N-2)/6개입니다. 그렇다면, 단색 삼각형이 아닌 삼각형의 개수는 어떻게 알 수 있을까요?

github

　’단색 삼각형이 아닌 삼각형’은 위의 사진에서 알 수 있듯 두 종류가 있습니다. 이때, 두 삼각형의 1번 꼭짓점을 봅시다. 두 삼각형 모두 1번 꼭짓점과 2번 꼭짓점을 연결하는 튜브와 1번 꼭짓점과 3번 꼭짓점을 연결하는 튜브의 색깔이 서로 다르다는 것을 알 수 있습니다. 3번 꼭짓점의 경우도 마찬가지로, 해당 꼭짓점을 연결하는 두 튜브의 색깔이 서로 다르다는 것을 알 수 있습니다. 종합하면, 어떤 삼각형이 단색 삼각형이 아닌 삼각형이라는 것은, 세 꼭짓점중 두 꼭짓점에 대해, 해당 꼭짓점을 연결하는 두 튜브의 색깔이 서로 다르다는 것을 의미한다는 것을 알 수 있습니다. 이를 이용하여, ‘같은 꼭짓점을 연결하는 두 튜브의 색깔이 다른 케이스의 수’를 모두 구한 후, 2를 나누면 O(n^3)에 단색 삼각형이 아닌 삼각형의 수를 구할 수 있습니다. 하지만, 당연하게도 이대로 풀면 시간초과를 받습니다.

　마지막 관찰은, 튜브의 색깔이 2개뿐이라는 데에서 시작합니다. 이로 인해, 원래대로라면 각 꼭짓점에 대해 n^2개의 경우를 모두 따져봐야 했지만, 이제는 (특정 꼭짓점과 연결된 파란 튜브 개수)*(특정 꼭짓점과 연결된 빨간 튜브 개수)로 구할 수 있습니다. 이렇게 하면 총 시간복잡도는 O(n^2)으로, 시간 내에 문제를 해결할 수 있습니다.

　구현 코드

　이해를 돕기 위해, 이번 포스팅에는 코드도 추가했습니다.

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
#include<cstdio>
#include<algorithm>

using namespace std;

int arr[1010][1010];

int main(){
    int t,n,ans,tmp;
    for(scanf("%d",&t);t--;){
        scanf("%d",&n);
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                scanf("%d",arr[i]+j);
                arr[j][i]=arr[i][j];
            }
        }
        ans=n*(n-1)*(n-2)/6,tmp=0;
        for(int i=0;i<n;++i){
            int one=0,zero=0;
            for(int j=0;j<n;++j){
                if(i==j)continue;
                arr[i][j]?++one:++zero;
            }
            tmp+=one*zero;
        }
        printf("%d\n",ans-tmp/2);
    }
}

　여담

　빨간색 튜브를 동맹관계, 파란색 튜브를 적대관계로 치환하면 부족 전쟁 문제도 동일하게 풀 수 있습니다.