SWEA 3421. 수제 버거 장인 by Java

ejjem·2025년 8월 10일

목록 보기

14/20

문제 풀이 날짜: 2025-08-10

💡Github URL

https://github.com/ejjem/coding-test/tree/main/SWEA/D5/3421.%E2%80%85%EC%88%98%EC%A0%9C%E2%80%85%EB%B2%84%EA%B1%B0%E2%80%85%EC%9E%A5%EC%9D%B8

💡문제에서 구해야 할 것

문제 조건
1번부터 N번까지 번호가 매겨진 총 N가지 재료가 존재함.
가능한 많은 종류의 버거를 만드려 하지만 같이 존재할 수 없는 재료가 존재함.
예를 들어 i번 재료와 j번 재료가 서로 궁합이 맞지 않는다면 이들을 동시에 포함한 버거는 만들 수 없음.
이렇게 궁합이 맞지 않는 재료들로 M개쌍에 대한 정보가 주였을 때 가능한 최대 버거의 종류를 찾기.
이 때, 어떤 두 버거가 정확하게 같은 종류의 재료들을 사용한다면 두 버거는 같은 종류의 버거로 봄.
재료가 0개인 경우도 버거로 포함.

제한시간: 2초 (Java)
입력
첫째 줄에 테스트 케이스 갯수가 주어짐.
각 테스트 케이스 별로 첫째 줄에 정수 N, M이 주어짐. (1 ≤ N ≤ 20, 0 ≤ M ≤ 400)
다음 M개의 줄에는 서로 다른 두 개의 숫자 a, b가 주어짐. (1 ≤ a, b ≤ N)
주어지는 쌍들은 모두 다르지는 않고, 즉 같은 쌍이 여러 번 주어질 수도 있음.
출력
각 테스트케이스 별로 순서대로 한 줄씩 답을 출력하는데, 제약조건을 만족시키며 만들 수 있는 버거의 가짓수를 출력.

💡알고리즘 설계

모든 버거의 가짓수는 N개의 재료로 만들 수 있는 부분 집합의 갯수와 같음.
따라서 이론상 완전 탐색으로 가능한 모든 부분 집합 2^N개를 만들고 제약 조건 위반 사항을 찾아도 최대 (2^20) * 400 이라 아슬아슬 하지만 2초 이내 연산이 가능하기는 함. 조금 더 최적화를 위해 백트래킹을 추가하려고 함.

비트 마스킹을 통해 재료 포함 여부, 제한 조건을 표현하고 n번 재료를 넣을 때 마다 제한 조건에 위배되는지 파악, 가능한 경우에만 재료를 넣음.

💡코드

메모리: 26,368 KB, 시간: 87 ms, 코드길이: 1,393 Bytes

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

public class Solution {
    static int N, M;
    static int[] conflict;
    static long ans;

    static void dfs(int idx, int chosen) {
    	// 종료 조건 
        if (idx == N) { ans++; return; }
        // 선택 x
        dfs(idx + 1, chosen);
        // 가능할 경우 선택 
        if ( (chosen & conflict[idx]) == 0 ) {
            dfs(idx + 1, chosen | (1 << idx));
        }
    }

    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());
            conflict = new int[N];
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken()) - 1;
                int b = Integer.parseInt(st.nextToken()) - 1;
                conflict[a] |= 1 << b;
                conflict[b] |= 1 << a;
            }
            ans = 0;
            dfs(0, 0);
            sb.append('#').append(tc).append(' ').append(ans).append('\n');
        }
        System.out.print(sb);
    }
}