https://www.acmicpc.net/problem/2422
2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데
첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번
www.acmicpc.net
문제생각
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
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 16439 치킨치킨치킨 - 완전탐색(DFS) JAVA (0) | 2023.07.12 |
---|---|
[백준] 5568 카드 놓기 - 완전탐색(DFS) JAVA (0) | 2023.07.12 |
[백준] 1969 DNA - 완전탐색 + 구현 JAVA (0) | 2023.07.10 |
[백준] 18511 큰 수 구성하기 - 완전탐색 + 문자열 JAVA (0) | 2023.07.09 |
[백준] 15721 번데기 - 완전탐색 + 구현 JAVA (0) | 2023.07.09 |