[SWEA] 27020. 인접 구역 색칠 경우의 수 (D2, Java)

1. 문제 요약

N개의 구역과 그 사이의 인접 관계 M개가 주어진다. K가지 색으로 모든 구역을 칠하되 인접한 두 구역은 서로 다른 색이어야 한다. 가능한 색칠 방법의 수를 구하면 된다.

제한 조건

• 1 ≤ N ≤ 10, 0 ≤ M ≤ N(N-1)/2, 1 ≤ K ≤ 5
• 테스트 케이스 T ≤ 50

2. 접근 과정

첫 번째 풀이 — 구역 순서대로 색 정하기

1번 구역부터 N번까지 순서대로 색을 결정한다. 어떤 색을 칠하려 할 때 이미 칠해진 구역 중 자신과 인접한 곳에 같은 색이 있으면 그 색은 건너뛴다.

3. 코드

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

public class Solution {

    static int n, k;
    static boolean[][] adj;
    static int[] group;
    static long answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine().trim());

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            adj = new boolean[n + 1][n + 1];
            group = new int[n + 1];
            answer = 0;

            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                adj[a][b] = true;
                adj[b][a] = true;
            }

            dfs(1, 0);

            sb.append('#').append(tc).append(' ').append(answer).append('\n');
        }

        System.out.print(sb);
    }

    static void dfs(int here, int used) {
        if (here > n) {
            answer += permutation(k, used);
            return;
        }

        int limit = Math.min(used + 1, k);

        for (int g = 1; g <= limit; g++) {
            if (!canJoin(here, g)) continue;

            group[here] = g;
            dfs(here + 1, Math.max(used, g));
            group[here] = 0;
        }
    }

    static boolean canJoin(int here, int g) {
        for (int prev = 1; prev < here; prev++) {
            if (adj[here][prev] && group[prev] == g) return false;
        }
        return true;
    }

    static long permutation(int K, int j) {
        long result = 1;
        for (int i = 0; i < j; i++) result *= (K - i);
        return result;
    }
}

각 단계에서 하는 일은 세 가지이다.

1. 종료 조건 — here > n이면 N개를 모두 칠했다는 뜻이다. 유효한 색칠 하나가 완성됐으므로 개수를 세고 돌아간다.
2. 선택 — 색 1번부터 K번까지 하나씩 시도한다.
3. 가지치기 — 이미 칠해진 구역 중 here와 인접한 곳에 같은 색이 있으면 그 색은 건너뛴다.

color[here] = c;      // 선택
dfs(here + 1);        // 다음 구역으로
color[here] = 0;      // 복구

시간복잡도: 최악 O(B(N) × N) — B(N)은 N개 원소의 분할 개수(벨 수)다.

공간복잡도: O(N²) — 인접 행렬. 재귀 깊이는 N으로 최대 10단계다.