[백준] 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 - 완전탐색(DFS) + 구현 JAVA

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

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

문제생각

DFS 문제입니다.

문제를 보면 섞어먹으면 안되는 조합의 번호가 주어지는데,

이떄 DFS를 통해 조합을 구한뒤, 섞어먹으면 안되는 조합의 번호인지 확인을 하여, 안되는 조합이라면 중단시키고,

섞어먹어도 되면 그대로 result++ 해주면 됩니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N, M;
	public static boolean[] visited;
	public static boolean[][] combination;
	public static int[] answer;
	public static int result = 0;
    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()); // 섞어먹으면 안되는 조합의 개수
    	
    	visited = new boolean[N + 1];
    	combination = new boolean[N+1][N+1];
    	answer = new int[3];
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int A = Integer.parseInt(st.nextToken());
    		int B = Integer.parseInt(st.nextToken());
    		combination[A][B] = true;
    		combination[B][A] = true;
    	}
    	simulate(1, 0);
    	System.out.println(result);
	}
    
    public static void simulate(int idx, int level) {
    	if(level == 3) {
    		
//    		for(int i=0;i<3;i++) {
//    			System.out.print(" "+answer[i]);
//    		}
    		for(int i=0;i<3;i++) {
    			for(int j=0;j<3;j++) {
    				if ( combination[answer[i]][answer[j]]  == true ) {
    					return ;
    				}
    			}
    		}
    		
    		result += 1;
    		return ;
    	}
    	
    	for(int i=idx;i<=N;i++) {
    		if(visited[i] == true) continue;
    		visited[i] = true;
    		answer[level] = i;
    		simulate(i+1, level + 1);
    		answer[level] = 0;
    		visited[i] = false;
    	}
    }
}

이 문제에서 idx의 조건을 다냐 안다냐에 따라서 조합이냐, 순열이느냐가 나뉩니다.

 

만약 idx의 조건을 넣은함수를 사용한다면, 조합은 원소의 중복을 허용하지 않고 조합을 구합니다. 

조합의 개수는 "n C r"으로 계산할 수 있습니다. 여기서 n은 원소의 개수, r은 조합의 길이입니다.

입력값
5 3
1 2
3 4
1 3
 
 
출력값
 1 2 3
 1 2 4
 1 2 5
 1 3 4
 1 3 5
 1 4 5
 2 3 4
 2 3 5
 2 4 5
 3 4 5
 
 결과값
 3

 

idx를 상관쓰지 않고한다면 순열이 나옵니다. 이유는 visited가 초기화되기에 그렇습니다.

순열은 원소의 개수를 n이라고 하고, 배열의 길이를 r이라고 할 때, 순열의 개수는 n! / (n-r)!입니다.

출력
5 3
1 2
3 4
1 3
 
순열 (idx값 사용안하여 visited 표시 안할시)
 1 2 3
 1 2 4
 1 2 5
 1 3 2
 1 3 4
 1 3 5
 1 4 2
 1 4 3
 1 4 5
 1 5 2
 1 5 3
 1 5 4
 2 1 3
 2 1 4
 2 1 5
 2 3 1
 2 3 4
 2 3 5
 2 4 1
 2 4 3
 2 4 5
 2 5 1
 2 5 3
 2 5 4
 3 1 2
 3 1 4
 3 1 5
 3 2 1
 3 2 4
 3 2 5
 3 4 1
 3 4 2
 3 4 5
 3 5 1
 3 5 2
 3 5 4
 4 1 2
 4 1 3
 4 1 5
 4 2 1
 4 2 3
 4 2 5
 4 3 1
 4 3 2
 4 3 5
 4 5 1
 4 5 2
 4 5 3
 5 1 2
 5 1 3
 5 1 4
 5 2 1
 5 2 3
 5 2 4
 5 3 1
 5 3 2
 5 3 4
 5 4 1
 5 4 2
 5 4 3