백준 32394번 4-cycle (그래프 활용)

1. 문제

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

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int MOD = 1_000_000_007;
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        boolean[][] nodes = new boolean[N + 1][N + 1];
        for (int i = 0; i < M; i++) {
            input = br.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);
            nodes[x][y] = nodes[y][x] = true;
        }
        long answer = 0;
        for (int i = 1; i < N; i++) {
            for (int j = i + 1; j <= N; j++) {
                long count = 0;
                for (int k = 1; k <= N; k++) {
                    if (k != i && k != j && nodes[k][i] && nodes[k][j]) count++;
                }
                answer += count * (count - 1) / 2;
            }
        }
        System.out.println(answer * 500_000_004 % MOD);
    }

}

3. 해설

1. 임의의 두 정점 i, j를 선택하여 공통 이웃인 정점의 개수를 카운팅한다.
2. 공통 이웃인 정점의 개수가 k일때 _kC₂ 개의 사이클이 생긴다.
   (4-사이클 이기 때문에 i,j를 제외한 2개의 정점이 필요하고
   역방향은 같은 사이클이기 때문에 순열이 아닌 조합을 사용)
3. 위의 조합에서 선택된 두 정점은 중복으로 i, j를 공통 이웃으로 두기 때문에 중복을 보정하여 2를 나눈다
   이때 문제의 조건에서 10^9+7으로 나눈 나머지를 출력하라고 했기 때문에 2를 나누는 대신 2의 모듈러 역원(500,000,004)을 곱해 보정한다.

4. 다른 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class FourCycle {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int MOD = 1_000_000_007;
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        boolean[][] nodes = new boolean[N + 1][N + 1];
        ArrayList<Pair> Edge = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            input = br.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);
            Edge.add(new Pair(x, y));
            nodes[x][y] = nodes[y][x] = true;
        }
        long answer = 0;
        for (int i = 0; i < M; i++) {
            for (int j = i + 1; j < M; j++) {
                int x1 = Edge.get(i).x, y1 = Edge.get(i).y, x2 = Edge.get(j).x, y2 = Edge.get(j).y;
                if (x1 == x2 || x1 == y2 || y1 == x2 || y1 == y2)
                    continue;
                if (nodes[x1][x2] && nodes[y1][y2])
                    answer++;
                if (nodes[x1][y2] && nodes[y1][x2])
                    answer++;
            }
        }
        System.out.println(answer * 500_000_004 % MOD);
    }

}

class Pair {
    int x, y;

    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

 

이 코드의 주요 장점

1. 시간 복잡도 개선
   • 기존 방법은 모든 정점 쌍에 대해 공통 이웃을 찾는 방식으로 O(N³)의 시간 복잡도를 가질 수 있다.
   • 이 풀이에서는 간선의 개수가 최대 1000이므로, 간선 쌍을 순회하는 O(M²)  접근법을 사용해 최대 약 1,000,000번의 반복만 수행한다.
2. 간결한 4사이클 판별:
   • 두 간선이 서로 겹치지 않는 (즉, 4개의 정점이 모두 다름) 경우에,
     {x1,y1}과 {x2,y2}가 주어지면,
     추가로 (x1,x2)와 (y1​,y2​)가 연결되어 있거나,
     (x1,y2)와 (y1,x2)가 연결되어 있으면 4사이클이 형성된다.

 

위 그림에서 검정선이 코드상의 i,j로 선택된 Pair 이고 파란선과 빨간선이 Pair로 선택되는 경우가 중복이므로 중복을 보정해준다.