수제 버거 장인
1. 문제 접근 방법 및 순서
이 문제는 특정 재료들을 함게 넣을 수 없다는 제약 조건이 걸린 부분 집합 구하기 문제입니다.
- 제약 사항 정리
- 인접 행렬을 활용해서 어떤 재료 조합이 불가능한지 저장합니다.
- 재귀적 탐색
- 1번 재료부터 N번 재료까지 포함할지 말지 결정하며 내려갑니다.
- 조건 검사
- 현재 재료를 선택하려고 할 때, 이미 선택된 재료를 중에 상극인 재료가 있는지 확인합니다.
- 카운팅
- 마지막 재료까지 결정을 마쳤다면 유효한 하나의 버거 조합이 완성된 것이므로 결과값을 증가시킵니다.
2. 필요 개념 및 알고리즘
- 백트래킹
- 재료의 개수 N이 최대 20입니다.
- 완전 탐색을 하더라도 충분히 시간 내에 들어올 수 있는 규모입니다.
- 인접 행렬
- 동시에 선택할 수 없는 재료 쌍이라는 문구에서 그래프의 간선 개념을 도출할 수 있습니다.
- 재료 A와 B는 함께 들어갈 수 없다라는 관계를 빠르게 조회하기 위함입니다.
3. 어려웠던 점
- 상극 관계 재료 체크
- 상극 관계 재료를 저장하고 체크하는지 방법을 찾지 못했습니다.
- 부분 집합 나열 방법
- 매개변수를 통해서 최대합을 구하는 부분 집합 문제를 풀었지만, 부분집합으로 나열하는 방법이 떠오르지 못했습니다.
4. 코드 풀이
4.1 부분 집합 나열 방법
static boolean[] select; // 재료를 선택했는지 체크하는 배열
select = new boolean[N + 1];
- 1 ~ N까지 재료들이 선택했는지 체크하기 위해 배열의 크기를 N+1로 합니다.
- 해당 재료가 선택되었는지, 미선택되었느지 확인하기 위해서 boolean 타입으로 합니다.
4.2 제약 사항 정리
static boolean[][] adj; // 금지 조합을 담을 인접 행렬
// 금지 조합 입력
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// 금지 조합 연결
adj[a][b] = adj[b][a] = true;
}
- 인접 행렬을 활용해서 어떤 재료 조합이 불가능한지 저장합니다.
- 조합이 불가능한 재료를 확인은 a,b 일 떄도 b,a일 때로 판단해야 하기 때문에 양방향으로 연결한 그래프로 생각합니다.
4.3 재귀적 탐색
// 선택
if (ischeck(level)) {
select[level] = true;
dfs(level + 1);
}
// 미선택
select[level] = false;
dfs(level + 1);
- 1번 재료부터 N번 재료까지 선택할지 선택 안할지 결정하며 내려갑니다.
4.4 조건 검사
static boolean ischeck(int level) {
// 현재까지 선택된 재료들과 비교
for (int i = 1; i < level; i++) {
// i번 재료를 선택했고, level과 상극인지 체크
if(select[i] && adj[level][i]) {
return false;
}
}
return true;
}
- 현재 재료를 선택하려고 할 때, 이미 선택된 재료들 중에 상극인 재료가 있는지 확인합니다.
4.5 카운팅
if (level == N + 1) {
result++;
return;
}
- 마지막 재료가지 결정을 마쳤다면 유효한 하나의 버거 조합이 완성된 것이므로 결과값을 증가시킵니다.
4.6 DFS 함수 코드
static void dfs(int level) {
// 종료 조건
// 1 ~ N까지 탐색하고, N+1에 도달하면 종료
if (level == N + 1) {
result++;
return;
}
// 선택
if (ischeck(level)) {
select[level] = true;
dfs(level + 1);
}
// 미선택
select[level] = false;
dfs(level + 1);
}
4.7 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static int N, M; // 재료의 수, 금지 조합의 수
static int result; // 버거의 가지수
static boolean[] select; // 재료를 선택했는지 체크하는 배열
static boolean[][] adj; // 금지 조합을 담을 인접 행렬
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine().trim());
// tc 수행
for (int tc = 1; tc <= T; tc++) {
// 재료의 수, 금지 조합의 수 입력
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 버거의 가지수, 체크 배열, 인접 행렬 초기화
result = 0;
select = new boolean[N + 1];
adj = new boolean[N + 1][N + 1];
// 금지 조합 입력
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// 금지 조합 연결
adj[a][b] = adj[b][a] = true;
}
// 처리
dfs(1);
// 출력 내용 추가
sb.append("#" + tc + " " + result + "\n");
} // tc 종료
// 출력
System.out.println(sb);
} // 메인 종료
// 부분 집합으로 재료의 조합을 나열하는 함수
static void dfs(int level) {
// 종료 조건
// 1 ~ N까지 탐색하고, N+1에 도달하면 종료
if (level == N + 1) {
result++;
return;
}
// 선택
if (ischeck(level)) {
select[level] = true;
dfs(level + 1);
}
// 미선택
select[level] = false;
dfs(level + 1);
}
// 금지 조합이 포함되었는지 체크하는 함수
// 금지된 조합을 찾으면 false 리턴
static boolean ischeck(int level) {
// 현재까지 선택된 재료들과 비교
for (int i = 1; i < level; i++) {
// i번 재료를 선택했고, level과 상극인지 체크
if(select[i] && adj[level][i]) {
return false;
}
}
return true;
}
}