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

문제 링크

2422-한윤정이 이탈리아에 가서 아이스크림을 사먹는데

입력

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

출력

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

문제 풀이

1. 브루트포스 알고리즘

내가 한건 Brute Force 방식
그냥 3중 for문을 이용해서 예외 처리를 해주는 방식이다.
의외로 2번보다 이 방법이 시간이 덜 걸렸음!

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        boolean[][] graph = new boolean[n][n];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;

            graph[a][b] = true;
            graph[b][a] = true;
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if(graph[i][j] || graph[i][k] || graph[j][k])continue;
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

2. 조합 사용

이거는 1번 방식으로 풀고나서 구글링하다가 알게 된 방식
어렵진 않다.

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

public class Main {
    static int n,m, ans;
    static int[] arr;

    static boolean[] visited;
    static boolean[][] graph;
    static int[] result;

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new boolean[n][n];
        visited = new boolean[n];

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

        result = new int[3];

        ans = 0;
        comb(0, 0);
        System.out.println(ans);
    }

    static void comb(int s, int depth) {
        if (depth == 3) {
            if (check()) {
                ans++;
            }
            return;
        }
        
        for (int i = s; i < n; i++) {
            if(visited[i] ) continue;
            visited[i] = true;
            result[depth] = i;
            comb(i, depth + 1);
            visited[i] = false;
        }
    }
    
    // 예외 조합인지 확인하는 함수
    static boolean check(){
        for (int i = 0; i < 2; i++) {
            for (int j = i + 1; j < 3; j++) {
                if (graph[result[i]][result[j]]) {
                    return false;
                }
            }
        }
        return true;
    }
}