[BOJ] 2422. 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 - BF (Java)

[BOJ] 2422. 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 - BF (Java)

Problem

제출일 : 2020-02-13

문제 풀이 시간 : 15M

난이도 : ☆

---

link : https://www.acmicpc.net/problem/2422

한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다.

input

첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 이상 나오지 않는다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000)

Output

첫째 줄에, 가능한 방법이 총 몇 개 있는지 출력한다.

Example

input

5 3
1 2
3 4
1 3

output

3

Solution & Inpression

순열을 이용하여 경우의 수를 구하고 금지된 조합일 경우 카운트를 하지 않는다.

Code

언어 : JAVA

메모리 : 34,032 kb

실행시간 : 104 ms

import java.util.Scanner;

public class Main {
    static int N, M, ans;
    static boolean[][] graph;
    static boolean[] visit;
    static int[] data = new int[3];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        graph = new boolean[N][N];
        visit = new boolean[N];

        for (int i = 0; i < M; i++) {
            int s = sc.nextInt() - 1;
            int e = sc.nextInt() - 1;
            graph[s][e] = true;
            graph[e][s] = true;
        }
        ans = 0;
        solve(0, 0);
        System.out.println(ans);

    }

    private static void solve(int index, int depth) {
        if (depth == 3) {
            if (check())
                ans++;
            return;
        }
        for (int i = index; i < N; i++) {
            if (!visit[i]) {
                visit[i] = true;
                data[depth] = i;
                solve(i, depth + 1);
                visit[i] = false;
            }
        }
    }

    private static boolean check() {
        for (int i = 0; i < 2; i++) {
            for (int j = i + 1; j < 3; j++) {
                if (graph[data[i]][data[j]])
                    return false;
            }
        }
        return true;
    }
}