[코딩테스트] SWEA 3421 수제 버거 장인(Java)

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 3421 수제 버거 장인입니다.

포인트

중·고등학교 때 배운 부분집합 개념을 떠올려 보면, 원소의 개수가 N개일 때 가능한 모든 부분집합의 수는 2ⁿ임을 알 수 있습니다.

이 문제에서도 모든 음식 조합(부분집합)을 고려하되, 서로 같이 먹으면 안 되는 음식 쌍(충돌 쌍)이 포함된 조합은 제외해야 합니다.

초기에는 DFS를 이용해 완전탐색을 시도했지만, 시간 초과가 발생하였고, 더 빠른 탐색 방식이 필요했습니다.

 

그 대안으로 선택한 것이 비트마스킹(bit masking)입니다.

비트마스킹은 집합의 포함 여부를 비트(0 또는 1)로 표현할 수 있기 때문에, 모든 조합을 효율적으로 순회할 수 있으며,
AND(&) 연산을 통해 충돌 여부도 매우 빠르게 판단할 수 있습니다.

이처럼 비트 연산은 속도가 빠르고, 메모리 효율도 뛰어나기 때문에,
이번 문제와 같이 부분집합을 다루는 경우에 매우 적합한 방법입니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {
    private static int tc, N, M;
    private static boolean[][] disabled;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int t = 1; t <= tc; t++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            long[][] conflict = new long[M][2];

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                long a = 1 << (Integer.parseInt(st.nextToken()) - 1);
                long b = 1 << (Integer.parseInt(st.nextToken()) - 1);
                conflict[i][0] = a;
                conflict[i][1] = b;
            }

            long count = 0;
            for (int i = 0; i < (1 << N); i++) {
                boolean check = false;
                for (int j = 0; j < M; j++) {
                    long foodA = conflict[j][0];
                    long foodB = conflict[j][1];
                    if ((i & foodA) != 0 && (i & foodB) != 0) {
                        check = true;
                        break;
                    }
                }
                if (!check) {
                    count++;
                }
            }
            sb.append("#").append(t).append(" ").append(count).append("\n");
        }
        System.out.println(sb);
    }
}
/*
3
3 2
1 2
2 3
3 0
3 3
1 2
1 3
2 3
 */

코드 설명

• long[][] conflict
  서로 함께 먹을 수 없는 음식 쌍을 저장하는 배열
  • 1 << (번호 - 1) 형태로 비트 마스크로 변환하여 저장합니다.
    (예: 음식 1 → 0001, 음식 3 → 0100)

for (int i = 0; i < (1 << N); i++) {
    boolean check = false;
    for (int j = 0; j < M; j++) {
        long foodA = conflict[j][0];
        long foodB = conflict[j][1];
        if ((i & foodA) != 0 && (i & foodB) != 0) {
            check = true;
            break;
        }
    }
    if (!check) {
        count++;
    }
}

• i는 0부터 2^N - 1까지의 모든 정수를 나타내며, 각 숫자가 하나의 부분집합을 의미합니다.
  • 예: i = 5 (101₂) → 음식 1과 음식 3을 선택한 경우
• conflict에 저장된 음식 쌍이 동시에 부분집합에 존재하면 해당 조합은 제외
  • (i & foodA) != 0 && (i & foodB) != 0 → 두 음식 모두 포함되었는지 확인
• 조건을 만족하는 조합(check == false)만 count++