백준 2242번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 [JAVA]

문제

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

 

입력

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

 

출력

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

 

예제

 

풀이 방법

이 문제는 섞어먹으면 안 되는 조합을 피하면서 아이스크림을 3가지 선택하는 방법의 수를 구하는 문제였습니다.

먼저 피해야하는 조합의 번호인 값을 icecream 2차원 배열에 true로 표시해주었습니다. 그리고 난 후, 아이스크림 3가지를 선택하기 위해 조합을 이용한 뒤, 3가지를 모두 선택한 후, 이 아이스크림이 섞어먹어도 괜찮은 조합인지 판단하기 위해 isCheck() 메서드를 통해 확인해 주었습니다. 만약 고른 아이스크림 조합의 icecream 배열 값이 true인 경우에는 섞어먹으면 안 되는 조합이 포함되어있는 경우이므로 false를 리턴해주었습니다. 반대로 for문을 다 끝냈다면 이 아이스크림 조합은 섞어먹어도 괜찮은 조합이므로 true를 리턴해 선택하는 방법의 수인 ans값을 +1 해주었습니다. 모든 조합의 결과를 확인 한 뒤, 총 선택할 수 있는 방법의 수를 출력해주었습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_BJ_2242_한윤정이이탈리아에가서아이스크림을사먹는데 {
    
    static int N,M,ans=0;
    static boolean [][] icecream;
    static boolean [] visited;
    static int [] select;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        icecream = new boolean[N][N];
        visited = new boolean[N];
        select = new int[3];
        
        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;
            
            icecream[a][b] = icecream[b][a] = true;
        }
        
        comb(0,0);
        System.out.println(ans);
 
    }
    
    public static void comb(int start,int cnt) {
        if(cnt==3) {
            if(isCheck()) ans++;
            return;
        }
        
        for(int i=start;i<N;i++) {
            if(!visited[i]) {
                visited[i] = true;
                select[cnt] = i;
                comb(i,cnt+1);
                visited[i] = false;
            }
        }
        
    }
    
    public static boolean isCheck() {
        for(int i=0;i<3;i++) {
            for(int j=i+1;j<3;j++) {
                if(icecream[select[i]][select[j]]) return false;
            }
        }
        return true;
    }
}