백준 26524번: 방향 정하기 Java Solution

1. Problem Definition & Analysis

$N$개의 정점을 가진 완전 그래프(Complete Graph)에서 모든 간선에 방향을 정해주었을 때 사이클을 형성하지 않도록 하는 경우의 수를 구하는 문제이다.

결론부터 말하자면 그냥 정점 개수에 팩토리얼을 취하면 된다. 근데 왜 팩토리얼일까? 이것이 이 문제의 가장 어려운 부분이다.

5개의 정점으로 이루어진 완전 그래프를 상상해 보라고 하면 대부분이 위와 같은 형태를 떠올릴 것이다. 저런 형태의 그래프를 떠올리면 이 문제를 해결하기가 매우 까다롭게 된다.

이 문제를 해결하는 핵심적인 아이디어는 정점들이 모든 정점 쌍에 대해 방문 순서를 식별할 수 있도록 완벽하게 위상 정렬되어 있다고 가정하는 것이다. 이를 수학적으로는 전순서(total order)로 정렬되어 있다고 말하는데, 설명의 편의를 위해 완벽하게 위상 정렬되어 있다라고 하겠다.

위 그래프처럼 1번이 가장 먼저 방문되고, 5번이 가장 나중에 방문되게끔 위상 정렬되어 있다고 가정하자. 간선의 총 개수는 10개이지만 정점들의 방문 순서를 명확히 나타내기 위해 4개만 표시하였다.

정점들이 완벽하게 위상 정렬되어 있다고 가정하면 모든 간선들의 방향이 강제된다는 것을 확인할 수 있다.

일단 위 그래프에 표시된 간선들의 방향이 우선 강제되었다. 그리고 또한 1번과 3번 정점 사이에 존재하는 간선의 방향은 무조건 1번에서 3번으로 향하도록 설정되어야 한다. 1번과 5번 정점 사이에 존재하는 간선의 방향 역시 1번에서 5번으로 향하도록 설정되어야 한다.

즉, 완전 그래프에 아주 많은 간선이 존재한다고 해도 방향 비순환 그래프(DAG, Directed Acyclic Graph)를 형성하고자 한다면 $N$개의 정점이 방문되는 순서만 정해주면 된다. 그러면 그래프에 존재하는 모든 간선의 방향은 강제된다. 이는 정점 개수에 순열을 취한 $N!$이다.

2. Solution

import java.util.*;
import java.io.*;

class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    static int N;
    static long[] factorial;
    static final long MOD = 1_000_000_007;
    
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        factorial = new long[N + 1];
        factorial[0] = 1;
        for (int i = 1; i <= N; i++)
            factorial[i] = ((long) i * (factorial[i - 1] % MOD)) % MOD;
        System.out.println(factorial[N]);
    }
}

정답 코드는 단순하다. $N!$을 구하고, 구하는 과정에서 모듈러 연산을 잘 추가해 주면 된다.

3. Conclusion

풀이 중 조금은 바보 같은 의문이 생겼다. 부끄럽지만 이 글을 읽는 다른 사람도 마주할 수 있는 것이므로 이에 대해서도 적어보겠다.

'$N - 1$개의 간선들의 방향만 정해주면 되는 것이므로 $2^{N-1}$도 경우의 수가 될 수 있지 않을까?'

이는 선형적인 그래프를 생각하면 발생할 수 있는 오류로, 유효하지 않다.

일단 $N - 1$개의 간선을 선택하는 데서부터 문제가 발생한다. 그러한 간선을 선택했을 때 간선들의 방향을 어떻게 설정하든 정점들이 완벽하게 위상 정렬될 수 있는가? 아니다.

예를 들어 앞서 살펴본 간선이 4개만 존재하는 선형 그래프에서 2번에서 3번으로 향하는 간선의 방향이 반대로 바뀌었다고 하자. 1번 정점이 먼저 방문되어야 하는지 5번 정점이 먼저 방문되어야 하는지 알 수 없게 된다.

또한, 위 그래프에 나타난 $N - 1$개의 방향이 정해진 간선들 역시 임의로 방향을 정한 것이 아닌 방문 순서에 의해 방향이 강제적으로 정해진 것이다.

우리는 처음에 정점들이 완벽하게 위상 정렬되어 있어 모든 정점 쌍에 대해 어떤 정점이 먼저 방문되는지 식별할 수 있다고 가정했다. 때문에 그 관계를 보일 수 있는 $N - 1$개의 간선만을 나타내 문제를 단순화한 것이다.

'25.09.03 기준 골드 5로 평가되어 있지만 이러한 발상을 요구하는 것은 결코 골드 5 수준이 아니라고 생각한다. 문제해결 과정에 비해 구현이 너무 단순해서 레이팅이 낮게 잡힌 것으로 보여 골드 3으로 기여했다.