[SWEA][Java] 3421. 수제 버거 장인

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWErcQmKy6kDFAXi

SW Expert Academy

 

문제 이해

N개의 재료와 M개의 금지 쌍이 주어진다.
금지 쌍에 포함된 재료는 동시에 같은 버거에 들어갈 수 없다.
조건을 만족하며 만들 수 있는 버거 조합의 가짓수를 구한다. (아무 재료도 넣지 않은 버거도 가능)

 

문제 풀이

💡 Backtracking (부분 집합)

• 가능한 모든 재료 조합의 개수를 세는 문제
  →  DFS로 모든 경우를 탐색해 카운트
• N ≤ 20이라 완전 탐색이 가능하다.
• 각 재료를 넣는다/안 넣는다 두 가지로 분기
  → 넣을 때는 이미 넣은 재료들과 충돌하지 않는지 확인

 

코드

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

public class Solution {

	static int n, m, ans;
	static List<Integer>[] list;
	static boolean[] selected;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= t; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			list = new ArrayList[n + 1];
			selected = new boolean[n + 1];
			ans = 0;

			for (int i = 0; i <= n; i++) {
				list[i] = new ArrayList<>();
			}

			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());

				list[a].add(b);
				list[b].add(a);
			}

			dfs(1);

			sb.append("#").append(tc).append(" ").append(ans).append("\n");
		}
		System.out.println(sb);
	}

	static boolean isPossible(int idx) {
		for (int i = 1; i <= n; i++) {
			if (selected[i] && list[i].contains(idx))
				return false;
		}
		return true;
	}

	static void dfs(int idx) {
		ans++;

		for (int i = idx; i <= n; i++) {
			if (selected[i] || !isPossible(i))
				continue;

			selected[i] = true;
			dfs(i + 1);
			selected[i] = false;
		}
	}
}