[백준 1278번] 연극

https://www.acmicpc.net/problem/1278

 

 

 

 

문제의 조건

1. N명을 가지고, 최대 K개의 장면을 만들어야 한다.
2. 한 장면에는 최소 1명의 배우가 있어야 한다.
3. 처음 장면과 마지막 장면에는 한 명만 존재해야 한다.
4. 장면이 바뀔 때마다 새로운 배우를 넣거나, 기존 배우를 하나 빼는 방법이 있다.
5. 각 장면마다 구성하는 배우들은 모두 달라야 한다.
6. 가능한 많은 배우들이 출연할 수 있도록 도와줘야 한다.

해당 문제를 풀 때에는 BackTracking, bit 연산을 이용해서 풀어주었다.

 

우선 최대한 배우들이 출연하면서 모든 장면에 다른 배우들이 나오려면 공집합을 제외한 부분집합의 개수를 구해주면 되므로

 

K = 2^N - 1 가 된다.

 

visited[] : 나올 수 있는 배우들의 장면 ( 1번 배우부터 각각 1번으로 생각하고 비트연산을 통해서 방문 여부 처리)

present[] : 현재 장면에 해당 배우가 존재하는지에 대한 유무 판단

List<Integer> li : 장면이 바뀔 때마다 업데이트되는 배우들의 번호를 추가해줬다.

boolean flag : 여러 경우의 수가 나와서 출력 값의 저장될 수 있으므로 제어

size: 마지막 장면에서 한 명의 배우만 나와야 하므로 간단하게 인자로 담아서 처리해줬다.

 

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

public class BOJ_G3_1278_연극 {
	static int N, K;
	static boolean[] present, visited;
	static StringBuilder sb;
	static boolean flag;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();

		flag = false;
		N = Integer.parseInt(br.readLine());
		present = new boolean[N + 1];
		visited = new boolean[(int)Math.pow(2, N)]; // 00 01 10 11

		K = (int)Math.pow(2, N) - 1; // 최대 장면의 개수
		List<Integer> li = new ArrayList<>();

		visited[1 << 0] = true;
		present[1] = true;
		li.add(1);

		play(1, 1, 1, li);

		System.out.println(sb);

	}

	static void play(int cnt, int curr, int size, List<Integer> li) {
		// 1 -> 1,2 -> 2 -> 0
		if (flag) return;
		if (size == 0) return;
		if (cnt == K && size == 1 && !flag) {
			flag = true;
			sb.append(K).append('\n');
			for(Integer i : li) {
				sb.append(i).append('\n');
			}

			for (int i = 1; i < N + 1; i++) {
				if (present[i]) {
					sb.append(i).append('\n');
					break;
				}
			}
			return;
		}

		for (int i = 1; i < N + 1; i++) {
			int bit = 1 << (i - 1);
			if (present[i]) {
				// 현재 장면에 있다면 빼는 경우의 수만 있음.
				int next = curr ^ bit;

				// but, 뺏을 때 이미 다른 장면에서 촬영했던 기록이 있다면 빼면 안됨.
				if (!isValid(next)) continue;
				if (visited[next]) continue;

				visited[next] = true;
				present[i] = false;
				li.add(i);
				play(cnt + 1, next, size-1, li);
				li.remove(li.size() - 1);
				present[i] = true;
				visited[next] = false;

			} else {
				// 현재 장면에 없다면 추가하는 경우의 수만 있음.
				int next = curr | bit;
				//  해당 배우를 추가해서 촬영한 기록이 있다면 추가하면 안됨.
				if (!isValid(next)) continue;
				if (visited[next]) continue;

				present[i] = true;
				visited[next] = true;
				li.add(i);
				play(cnt + 1, next, size+1, li);
				li.remove(li.size() - 1);
				present[i] = false;
				visited[next] = false;

			}
		}
	}

	static boolean isValid(int x) {
		return x != 0;
	}
}

 

 

 

나의 방식이 효율적인 방식은 아닌 것 같다. 아무래도 재귀 호출 함수를 통한 풀이이므로 2^N -1 번의 호출을 가지게 된다.

문제에서 N <= 17이기 때문에 시간초과는 나지 않았던 것 같지만, N의 값이 30이상이 된다면 시간초과가 날 것이다.