[백준] code.plus(브루트 포스 Part 1,JAVA)2422번, 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

문제 링크

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

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. N종류의 아이스크림이 존재합니다.

2. M개의 조합은 섞어먹으면 안됩니다.

3. 먹을 수 있는 아이스크림의 조합의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. M개의 조합이 되지 않는 아이스크림 조합의 모든 경우를 탐색합니다.

 

3. 탐색이 종료한 뒤에 나올 수 있는 조합의 개수를 결과로 출력합니다.

 

조합관련

 

N개를 이용하여 만들 수 있는 조합을 만든 후

 

M개의 조합이 섞여있는지 확인합니다.

 

섞인 경우

 

해당 경우를 넘어갑니다.

 

섞이지 않은 경우

 

조건에 만족하므로 개수 + 1을 진행합니다.

 

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

 

N = 5, M = 3

M개의 조합

(1, 2)

(3, 4)

(1, 3)

 

2. M개의 조합이 되지 않는 아이스크림 조합의 모든 경우를 탐색합니다.

 

1 2 3 : (1, 2) : X
1 2 4 : (1, 2) : X
1 2 5 : (1, 2) : X
1 3 4 : (1, 3),(3, 4) : X
1 3 5 : (1, 3) : X
1 4 5 : O
2 3 4 : (3, 4) : X
2 3 5 : O
2 4 5 : O
3 4 5 : (3, 4) : X

 

3. 탐색이 종료한 뒤에 나올 수 있는 조합의 개수를 결과로 출력합니다.

 

나올 수 있는 조합의 개수 3을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력값을 띄어쓰기 기준으로 나누었습니다.
• search함수를 실행하여 만들 수 있는 조건에 만족하는 모든 조합의 개수를 구합니다.
• 조합의 개수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 재귀를 이용하여 아이스크림 조합의 모든 경우를 구한 뒤 selectCheck를 실행합니다.
• selectCheck함수는 M개의 조합이 포함되었는지 확인 및 조건에 만족하면 개수 +1을 진행합니다.

 

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] check;	//M개 조합 저장 배열
    static int[] select = new int[3];	//선택한 아이스크림 저장 배열
    static int N,M, answer = 0;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st= new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        check = new boolean[N+1][N+1];
        //입력값 저장
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine()," ");
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            check[n1][n2] = true;
            check[n2][n1] = true;
        }
        //아이스크림 모든 조합 만들기
        for(int i=1;i<=N;i++){
            select[0] = i;
            search(1, i);
        }
        bw.write(answer + "");	//조건 만족하는 조합 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //아이스크림 조합 모든 경우 만드는 재귀 함수
    static void search(int depth, int index){
        if(depth==3){
            selectCheck();	//조건에 만족하는지 확인
            return;
        }
        //탐색
        for(int i=index+1;i<=N;i++){
            select[depth] = i;
            search(depth+1, i);
        }
    }
    //조건에 만족하는지 확인 및 개수 증가 함수
    static void selectCheck(){
        for(int i=0;i<3;i++){
            for(int j=i+1;j<3;j++){
                if(check[select[i]][select[j]])	//M조합이 해당 경우에 존재시
                   return;
            }
        }
        //M조합이 해당 경우에 존재 X일 때
        answer++;
    }
}