[알고리즘] 백준 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 - JAVA

www.acmicpc.net/problem/2422

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

문제 설명

입력으로 N개의 아이스크림과 M개의 예외가 주어진다.

 

N개의 아이스크림중 3개를 골랐을 때, 예외 사항과 겹치지 않는 경우의 수의 개수를 구하면 된다.

 

풀이과정

N(C)3을 모두 구한다음 예외 사항을check하면 된다.

 

예외사항을 체크하기위해 2중반복문을 돌렸는데 이러면 시간초과가 뜬다.

 

그래서 그래프를 만들어서 예외사항을 체크했다.

 

이 문제처럼 입력이 주어지면 그래프를 만드는 습관을 들여야 할 것 같다.

 

백트래킹 소스코드

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

class Main {

    static int N;
    static int M;
    static int[] selectedIceCream = new int[3];
    static boolean[][] map;
    static int result = 0;

    static boolean visited[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new boolean[N + 1][N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i < M; i++) {
            s = br.readLine();
            st = new StringTokenizer(s, " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            map[x][y] = true;
            map[y][x] = true;
        }

        backTracking(0, 1);
        System.out.println(result);

    }

    static void backTracking(int depth, int index) {
        if (depth == 3) {
            if (check())
                result++;
            return;
        }

        for (int i = index; i < N + 1; i++) {
            if (!visited[i]) {
                visited[i] = true;
                selectedIceCream[depth] = i;
                backTracking(depth + 1, i + 1);
                visited[i] = false;
            }
        }
    }

    static boolean check() {

        for (int i = 0; i < 3; i++) {
            for (int j = i + 1; j < 3; j++) {
                if (map[selectedIceCream[i]][selectedIceCream[j]])
                    return false;
            }
        }

        return true;
    }

}

 

Brute Force 소스코드

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

class Main {

    static int N;
    static int M;
    static boolean[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new boolean[N + 1][N + 1];

        for (int i = 0; i < M; i++) {
            s = br.readLine();
            st = new StringTokenizer(s, " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            map[x][y] = true;
            map[y][x] = true;
        }

        System.out.println(bruteForce());

    }

    static int bruteForce() {
        int count = 0;

        for (int i = 1; i < N + 1; i++) {
            for (int j = i + 1; j < N + 1; j++) {
                for (int k = j + 1; k < N + 1; k++) {
                    if (map[i][j] || map[i][k] || map[j][k])
                        continue;
                    count++;
                }
            }
        }
        return count;
    }

}